Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class WordDictionary {
- private:
- int nodes;
- vector<int> mx;
- vector<vector<int>> trie;
- public:
- WordDictionary() {
- nodes = 1;
- mx.push_back(0);
- trie.emplace_back(26, -1);
- }
- void addWord(string word) {
- addWord(word, 0, 0);
- cout << mx[0] << "\n";
- }
- bool search(string word) {
- return search(word, 0, 0);
- }
- private:
- int addWord(string &word, int node, int i) {
- cout << node << " " << i << "\n";
- if (i >= (int) word.size()) {
- cout << "returning\n";
- return mx[node] = 1;
- }
- char c = word[i];
- if (trie[node][c - 'a'] == -1) {
- mx.push_back(0);
- trie.emplace_back(26, -1);
- trie[node][c - 'a'] = nodes++;
- }
- mx[node] = max(mx[node], addWord(word, trie[node][c - 'a'], i + 1) + 1);
- cout << node << " " << mx[node] << "\n";
- return mx[node];
- }
- bool search(string &word, int node, int i) {
- if (node == -1) {
- return false;
- }
- if (i >= (int) word.size()) {
- return true;
- }
- if (word[i] != '.') {
- return search(word, trie[node][word[i] - 'a'], i + 1);
- }
- for (char c = 'a'; c <= 'z'; c++) {
- if (search(word, trie[node][c - 'a'], i + 1)) {
- return true;
- }
- }
- return false;
- }
- };
- /**
- * Your WordDictionary object will be instantiated and called as such:
- * WordDictionary* obj = new WordDictionary();
- * obj->addWord(word);
- * bool param_2 = obj->search(word);
- */
Add Comment
Please, Sign In to add comment