fork download
copy 
  1. #include<iostream>
  2. #include<string>
  3. #include<vector>
  4. #include<unordered_set>
  5. using namespace std;
  6. class TrieNode {
  7. public:
  8. 	bool isWord;
  9. 	TrieNode * subTrie[26];
  10. 	TrieNode() {
  11. 		isWord = false;
  12. 		for (int i = 0; i < 26; i++)
  13. 			subTrie[i] = NULL;
  14. 	}
  15. };
  16. class Trie {
  17. private:
  18. 	TrieNode * root;
  19. public:
  20. 	Trie() {
  21. 		root = new TrieNode();
  22. 	}
  23. 	~Trie() {
  24. 		destruct(root);
  25. 		if (root != NULL)
  26. 			delete root;
  27. 	}
  28. 	void destruct(TrieNode * node) {
  29. 		if (node == NULL) return;
  30. 		for (int i = 0; i < 26; i++) {
  31. 			if (node->subTrie[i] != NULL) {
  32. 				destruct(node->subTrie[i]);
  33. 				delete node->subTrie[i];
  34. 			}
  35. 		}
  36. 	}
  37. 	void addWord(string word) {
  38. 		TrieNode * curr = root;
  39. 		for (int i = 0; i < word.length(); i++) {
  40. 			int idx = word[i] - 'A';
  41. 			if (idx < 0 || idx > 25) continue;
  42. 			if (curr->subTrie[idx] == NULL) {
  43. 				curr->subTrie[idx] = new TrieNode();
  44. 			}
  45. 			curr = curr->subTrie[idx];
  46. 		}
  47. 		curr->isWord = true;
  48. 	}
  49. 	string searchSet(vector<unordered_set<char>> &setSet, string &word, unsigned int maxDepth) {
  50. 		TrieNode *curr = root;
  51. 		int depth = 0;
  52. 		bool gotAbsent = false;
  53. 		unordered_set<char>::iterator itr = setSet[depth].begin();
  54. 		// breath first search
  55. 		for (; itr != setSet[depth].end(); itr++) {
  56. 			int idx = (*itr) - 'A';
  57. 			if (curr->subTrie[idx] == NULL) {
  58. 				// continue depth first search
  59. 				word[depth] = *itr;
  60. 				gotAbsent = true;
  61. 				break;
  62. 			}
  63. 		}
  64. 		if (gotAbsent) {
  65. 			return word;
  66. 		} else {
  67. 			if (searchNextLevel(curr, depth, word, setSet, maxDepth)) {
  68. 				return word;
  69. 			} else {
  70. 				return "-";
  71. 			}
  72. 		}
  73. 	}
  74. 	bool searchNextLevel(TrieNode *curr, int depth, string &word, vector<unordered_set<char>> &setSet, unsigned int maxDepth) {
  75. 		if (depth >= maxDepth - 1) {
  76. 			return false;
  77. 		}
  78. 		bool gotAbsent = false;
  79. 		unordered_set<char>::iterator itr = setSet[depth].begin();
  80. 		for (; itr != setSet[depth].end(); itr++) {
  81. 			int idx = (*itr) - 'A';
  82. 			gotAbsent = false;
  83. 			TrieNode* nextCurr = curr->subTrie[idx];
  84. 			word[depth] = *itr;
  85. 			unordered_set<char>::iterator itr2 = setSet[depth + 1].begin();
  86. 			for (; itr2 != setSet[depth + 1].end(); itr2++) {
  87. 				int idx2 = (*itr2) - 'A';
  88. 				if (nextCurr->subTrie[idx2] == NULL) {
  89. 					word[depth + 1] = *itr2;
  90. 					gotAbsent = true;
  91. 					break;
  92. 				}
  93. 			}
  94. 			if (gotAbsent) {
  95. 				return true;
  96. 			} else {
  97. 				if (searchNextLevel(nextCurr, depth + 1, word, setSet, maxDepth)) {
  98. 					return true;
  99. 				}
  100. 			}
  101. 		}
  102. 		return false;
  103. 	} // end of function
  104. };
  105. class MyMap {
  106. public:
  107. 	vector<unordered_set<char>> setSet;
  108. 	Trie trie;
  109. 	string aWord;
  110. 	unsigned int N;
  111. 	unsigned int L;
  112. 	MyMap(unsigned int n, unsigned int l) {
  113. 		N = n;
  114. 		L = l;
  115. 		setSet = vector<unordered_set<char>>(L);
  116. 	}
  117. 	void insertSet(int y, char C) {
  118. 		if (setSet[y].find(C) == setSet[y].end()) {
  119. 			(setSet[y]).insert(C);
  120. 		}
  121. 	}
  122. 	void insertTrie(string word) {
  123. 		aWord = word;
  124. 		trie.addWord(word);
  125. 	}
  126. 	string calculateResult() {
  127. 		unsigned int n = 1;
  128. 		for (int i = 0; i < L; i++) {
  129. 			n = n * setSet[i].size();
  130. 		}
  131. 		if (n <= N) {
  132. 			return "-";
  133. 		} else {
  134. 			return trie.searchSet(setSet, aWord, L);
  135. 		}
  136. 	}
  137. };
  138. int main() {
  139. 	unsigned int T = 0, N = 0, L = 0;
  140. 	string word;
  141. 	cin >> T;
  142. 	for (int i = 0; i < T; i++) {
  143. 		cin >> N;
  144. 		cin >> L;
  145. 		MyMap myMap(N, L);
  146. 		for (int x = 0; x < N; x++) {
  147. 			cin >> word;
  148. 			myMap.insertTrie(word);
  149. 			for (int y = 0; y < L; y++) {
  150. 				myMap.insertSet(y, word[y]);
  151. 			}
  152. 		}
  153. 		string re = myMap.calculateResult();
  154. 		cout << "Case #" << i + 1 << ": " << re << endl;
  155. 	}
  156. 	return 0;
  157. }
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
5
4 1
A
B
C
D
4 2
WW
AA
SS
DD
4 2
AA
AB
BA
BB
3 4
CAKE
TORN
SHOW
5 7
HELPIAM
TRAPPED
INSIDEA
CODEJAM
FACTORY
stdout
copy 
Case #1: -
Case #2: DS
Case #3: -
Case #4: SOOW
Case #5: FECTORY
https://ideone.com/OeN0s7
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!