#include<bits/stdc++.h> using namespace std; class TrieNode { public: char data; TrieNode ** children; bool isEndOfString = false; TrieNode(char data) { this->data = data; children = new TrieNode*[26]; for (int i = 0; i < 26; ++i) { children[i] = NULL; } isEndOfString = false; } }; class Trie { TrieNode *root; public: Trie() { root = new TrieNode ('\0'); } private: void insertWord(TrieNode *root , string word) { //base case if (word.size() == 0) { root->isEndOfString = true; return; } //small calculation int index = word[0] - 'a'; //for 0th letter // a-0 b-1 c-2 d-3 e-4 f-5 g-6---y-24 z-25 //now check at that particular index TrieNode * child; if (root->children[index] == NULL) { //make new node and put its address childern ptr child = new TrieNode(word[0]); root-> children[index] = child; } else { child = root->children[index]; //child will take address for recursive call } //recursion from index one insertWord(child , word.substr(1)); } public: void insertWord(string word) { return insertWord(this->root , word); } private: bool search(TrieNode*root , string word) { if (word.size() == 0) { return root->isEndOfString; } TrieNode *child; int index = word[0] - 'a'; if ( root->children[index] != NULL) { child = root->children[index]; } else return false; return search(child , word.substr(1)); } public: bool search(string word) { return search(this->root, word); } void display(TrieNode* node , string word, vector<string> & v) { if (node->isEndOfString == true) { // cout << word << endl; v.push_back(word); } TrieNode * child; for (int i = 0; i < 26; ++i) { if (node->children[i] != NULL ) { child = node->children[i]; display(child , word + node->children[i]->data, v); } } } void display() { string word = ""; vector <string> v; display(root, word , v); } private: TrieNode* autoComplete(TrieNode*node , string word) { if ( word.length() == 0) return node; TrieNode *child; int index = word[0] - 'a'; if ( node->children[index] != NULL) { child = node->children[index]; } else return NULL; TrieNode * n = autoComplete(child , word.substr(1)); return n; } public: void autoComplete(string word) { string a = word; TrieNode*node = autoComplete(root, word); // cout << node->data << endl; if (node) { vector<string>v; display(node , word, v ); cout << v.size() << endl; for (int i = 0; i < v.size(); ++i) { cout << v[i] << endl; } } else { cout << "\n Not a valid word to autoComplete:" << endl; } } int distance(string str1 , string str2) { int cost = 0; int m = str1.length(); int n = str2.length(); int lev[m + 1][n + 1]; for (int i = 0; i <= m; ++i) { for (int j = 0; j <= n; ++j) { lev[i][j] = 0; } } for (int i = 0; i <= m; i++) lev[i][0] = i; for (int j = 0; j <= n; j++) lev[0][j] = j; for (int j = 1; j <= n; ++j) { for (int i = 1; i <= m; ++i) { if (str1[i] == str2[j]) cost = 0 ; else cost = 1; lev[i][j] = min(lev[i - 1][j - 1] + cost, min(1 + lev[i - 1][j], 1 + lev[i][j - 1])); } } return lev[m][n]; } void edit_dis_word(TrieNode*node, string word , string lev_word , vector<string>&v) { if (node->isEndOfString == true) { int k = distance(word , lev_word); if (k <= 3) v.push_back(word); } TrieNode * child; for (int i = 0; i < 26; ++i) { if (node->children[i] != NULL ) { child = node->children[i]; edit_dis_word(child , word + node->children[i]->data, lev_word, v); } } } void autoCorrect(string lev_word) { vector<string>matching; //for storing the lev_distance owrd edit_dis_word(root , "" , lev_word, matching); cout << matching.size() << endl; for (int i = matching.size() - 1; i >= 0 ; i--) { cout << matching[i] << endl; } } }; int main() { #ifdef ONLINE_JUDGE freeopen("input.txt", "r", stdin); freeopen("output.txt", "r", stdin); #endif int num_words; int q; cin >> num_words >> q; Trie t; string word; while (num_words--) { cin >> word; t.insertWord(word); } int choice; while (q--) { cin >> choice; if (choice == 1) // spell check { cin >> word; cout << (t.search(word) ? "1\n" : "0\n"); } else if (choice == 2) //auto complete { cin >> word; t.autoComplete(word); } else if (choice == 3) { cin >> word; t.autoCorrect(word);// autoCorrect } } // t.display(); return 0; }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter