[C++]白駿5052号:電話番号リスト

質問リンク

5052：電話番号リスト

問題の概要

指定された電話番号で、どの電話番号が他の電話番号の接頭辞であるかを判別します.

方法

明かりで解いたまず、指定されたすべての電話番号を入力としてトレイに入れます.その後、各電話番号の順にトレイをナビゲートします.電話番号の最後の番号に対応するノードに到達し、サブノードが存在する場合、電話番号は他の電話番号のプレフィックスであってもよい.
今日初めてTrayを勉強しましたが、他の文字列アルゴリズム(例えばKMP)よりも理解しやすいので、面白く解けました.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

struct Trie {
	Trie* child[10];

	Trie() {
		for (int i = 0; i < 10; i++)
			child[i] = NULL;
	}

	void insert(string& numbers, int idx) {
		if (idx == numbers.size())
			return;

		if (child[numbers[idx] - '0'] == NULL) {
			Trie* trie = new Trie();
			child[numbers[idx] - '0'] = trie;
		}

		child[numbers[idx] - '0']->insert(numbers, idx + 1);
	}

	bool check(string& numbers, int idx) {
		if (idx == numbers.size()) {
			for (int i = 0; i < 10; i++)
				if (child[i] != NULL)
					return false;
			return true;
		}

		if (!child[numbers[idx] - '0']->check(numbers, idx + 1))
			return false;
		return true;
	}

	void clear(void) {
		for (int i = 0; i < 10; i++) {
			if (child[i] != NULL) {
				child[i]->clear();
				delete child[i];
			}
		}
	}
};

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;

	while (t--) {
		int n;
		cin >> n;

		Trie* root = new Trie();

		vector<string> v(n);
		for (int i = 0; i < n; i++)
			cin >> v[i];
		
		for (auto& i : v)
			root->insert(i, 0);

		bool flag = false;
		for (auto& i : v) {
			if (!root->check(i, 0)) {
				flag = true;
				break;
			}
		}

		cout << (flag ? "NO\n" : "YES\n");
		root->clear();
		delete root;
	}

	return 0;
}