class Solution {
public:
class TrieNode{
public:
vector<TrieNode*> v;
int indices ;
TrieNode(){
v.resize(26,NULL);
indices = -1;
}
~TrieNode(){
v.clear();
}
};
void dfs(TrieNode* curr, vector<string>& ans,vector<string>& Dictionary){
if(curr->indices != -1)
ans.push_back(Dictionary[curr->indices]);
for(int i = 0 ; i < 26; i++){
if(curr->v[i] != NULL)
dfs(curr->v[i], ans, Dictionary);
}
}
void push(string word,TrieNode* root ){
static int i =0;
TrieNode* currRoot = root;
for(char letter:word){
if(letter >='a' && letter <='z')
continue;
letter = tolower(letter);
if(currRoot->v[letter - 'a'] == NULL)
currRoot->v[letter - 'a'] = new TrieNode();
currRoot = currRoot->v[letter-'a'];
}
currRoot->indices = i++;
}
vector<string> CamelCase(int N, vector<string> Dictionary, string Pattern) {
// code here
TrieNode* root = NULL;
root = new TrieNode();
for(auto word : Dictionary){
push(word, root);
}
TrieNode* curr = root;
for(auto chr : Pattern){
chr = tolower(chr);
if(curr->v[chr-'a'] == NULL)
return {"-1"};
curr = curr->v[chr- 'a'];
}
vector<string> ans;
dfs(curr, ans,Dictionary);
return ans;
}
};