I have run successfully in my local machine. Not sure why it generate a runtime
error when I submited.
#include<iostream>
#include<string>
#include<vector>
#include<unordered_set>
using namespace std;
class TrieNode {
public:
bool isWord;
TrieNode * subTrie[26];
TrieNode() {
isWord = false;
for (int i = 0; i < 26; i++)
subTrie[i] = NULL;
}
};
class Trie {
private:
TrieNode * root;
public:
Trie() {
root = new TrieNode();
}
~Trie() {
destruct(root);
if (root != NULL)
delete root;
}
void destruct (TrieNode * node) {
if (node == NULL) return;
for (int i = 0; i < 26; i++) {
if (node->subTrie[i] != NULL) {
destruct(node->subTrie[i]);
delete node->subTrie[i];
}
}
}
void addWord(string word) {
TrieNode * curr = root;
for (int i = 0; i < word.length(); i++) {
int idx = word[i] - 65;
if (idx < 0 || idx >25) continue;
if (curr->subTrie[idx] == NULL) {
curr->subTrie[idx] = new TrieNode();
}
curr = curr->subTrie[idx];
}
curr->isWord = true;
}
string searchSet(vector<unordered_set<char>> &setSet, string &word,
unsigned int maxDepth)
{
TrieNode *curr = root;
int depth = 0;
bool gotAbsent = false;
unordered_set<char>::iterator itr = setSet[depth].begin();
// breath first search
for(;itr != setSet[depth].end(); itr++)
{
int idx = (*itr) - 65;
if (curr->subTrie[idx] == NULL)
{
// continue depth first search
word[depth] = *itr;
gotAbsent = true;
break;
}
}
if (gotAbsent)
{
return word;
}
else
{
if (searchNextLevel(curr, depth, word, setSet,
maxDepth))
{
return word;
}
else
{
return "-";
}
}
}
bool searchNextLevel(TrieNode *curr, int depth, string &word,
vector<unordered_set<char>> &setSet, unsigned int maxDepth)
{
if (depth >= maxDepth-1)
{
return false;
}
bool gotAbsent = false;
unordered_set<char>::iterator itr = setSet[depth].begin();
for(;itr != setSet[depth].end(); itr++)
{
int idx = (*itr) - 65;
gotAbsent = false;
curr = curr->subTrie[idx];
word[depth] = *itr;
unordered_set<char>::iterator itr2 =
setSet[depth+1].begin();
for (;itr2 != setSet[depth+1].end(); itr2++)
{
int idx2 = (*itr2) - 65;
if (curr->subTrie[idx2] == NULL)
{
word[depth+1] = *itr2;
gotAbsent = true;
break;
}
}
if (gotAbsent)
{
return true;
}
else
{
if (searchNextLevel(curr, depth+1, word,
setSet, maxDepth))
{
return true;
}
}
}
return false;
} // end of function
};
class MyMap
{
public:
vector<unordered_set<char>> setSet;
Trie trie;
string aWord;
unsigned int N;
unsigned int L;
MyMap(unsigned int n, unsigned int l)
{
N = n;
L = l;
setSet = vector<unordered_set<char>>(L);
}
void insertSet(int y, char C)
{
if (setSet[y].find(C) == setSet[y].end())
{
(setSet[y]).insert(C);
}
}
void insertTrie(string word)
{
aWord = word;
trie.addWord(word);
}
string calculateResult()
{
unsigned int n = 1;
for (int i = 0; i < L; i++)
{
n = n * setSet[i].size();
}
if (n <= N)
{
return "-";
}
else
{
return trie.searchSet(setSet, aWord, L);
}
}
};
int main()
{
unsigned int T = 0, N = 0, L = 0;
string word;
cin >> T;
for (int i = 0; i < T; i++)
{
cin >> N;
cin >> L;
MyMap myMap(N, L);
for (int x = 0; x < N; x++)
{
cin >> word;
myMap.insertTrie(word);
for (int y = 0; y < L; y++)
{
myMap.insertSet(y, word[y]);
}
}
string re = myMap.calculateResult();
cout << "Case #" << i+1 << ": " << re << endl;
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/c5bd7ce6-c24e-439a-ae9d-a306d2360827%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
