fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Trie {
  5. private:
  6.     static const int chars = 26;
  7.     Trie* child[chars];
  8.     bool isLeaf{};
  9.  
  10. public:
  11.     Trie() {
  12.         memset(child, 0, sizeof(child));
  13.     }
  14.     ~Trie() {
  15.         for (int i = 0; i < chars; i++) {
  16.             if (child[i]) {
  17.                 delete child[i];
  18.             }
  19.         }
  20.     }
  21.  
  22.     void insert(const string& s, int idx = 0) {
  23.         if (idx == s.length()) {
  24.             isLeaf = true;
  25.         } else {
  26.             int cur = s[idx] - 'a';
  27.             if (child[cur] == nullptr) {
  28.                 child[cur] = new Trie();
  29.             }
  30.             child[cur]->insert(s, idx + 1);
  31.         }
  32.  
  33.     }
  34.  
  35.     bool wordExists(const string& s, int idx = 0) const {
  36.         if (idx == s.size()) return isLeaf;
  37.         int cur = s[idx] - 'a';
  38.         if (!child[cur]) return false;
  39.         return child[cur]->wordExists(s, idx + 1);
  40.     }
  41.  
  42.     bool prefixExists(const string& s, int idx = 0) const {
  43.         if (idx == s.size()) return true;
  44.         int cur = s[idx] - 'a';
  45.         if (!child[cur]) return false;
  46.         return child[cur]->prefixExists(s, idx + 1);
  47.     }
  48.  
  49.     bool SuffixExists(const string& s ) {
  50.         for(int i = 0; i < s.length();i++){
  51.             if(wordExists(s.substr(i))){
  52.                 return true;
  53.             }
  54.         }
  55.         return false;
  56.     }
  57.     //Problem 1:
  58.     void getAllstrings(vector<string>& res, string s = "") {
  59.     if (isLeaf) {
  60.         res.push_back(s);
  61.     }
  62.     for (int i = 0; i < 26; i++) {
  63.         if (child[i]) {
  64.             child[i]->getAllstrings(res, s + char(i + 'a'));
  65.         }
  66.     }
  67.     }
  68.    //Problem 2:
  69.     void autoComplete(string s){
  70.         vector<string>allWords;
  71.         getAllstrings(allWords);
  72.         for(auto word: allWords){
  73.             if(word.substr(0, s.length()) == s){
  74.                 cout<<word<<endl;
  75.             }
  76.         }
  77.  
  78.     }
  79.     //Problem 3 : 
  80.     bool findModifiedWord(string s) {
  81.         for (int i = 0; i < s.length(); i++) {
  82.             char original = s[i];
  83.             for (char j = 'a'; j <= 'z'; j++) {
  84.                 if (j != original) {
  85.                     s[i] = j;
  86.                     if (wordExists(s)) {
  87.                         return true;
  88.                     }
  89.                 }
  90.             }
  91.             s[i] = original;
  92.         }
  93.         return false;
  94.     }
  95.  
  96. };
  97.  
  98. int main() {
  99. 	string s; cin >> s;
  100.     Trie tree;
  101.     tree.insert("abcd");
  102.     tree.insert("ab");
  103.     tree.insert("abx");
  104.     tree.insert("abyz");
  105.     tree.insert("xyz");
  106.     tree.insert("a");
  107.     tree.insert("bcd");
  108.     vector<string> res;
  109.     tree.getAllstrings(res);
  110.     cout <<"all strings in the trie\n";
  111.     for(auto s: res){
  112.         cout<<s<<endl;
  113.     }
  114.     cout <<"--------------------------------\n";
  115.     cout <<"auto complete of ab\n";
  116.     tree.autoComplete("ab");
  117.     cout <<"--------------------------------\n";
  118.     cout << boolalpha <<tree.findModifiedWord("bcy") <<endl;
  119.     cout << boolalpha <<tree.findModifiedWord("abyx") <<endl;   
  120.     cout << boolalpha <<tree.findModifiedWord("manar") <<endl;
  121.  
  122.     return 0;
  123. }
  124.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Trie homework 2
stdout
copy 
all strings in the trie
a
ab
abcd
abx
abyz
bcd
xyz
--------------------------------
auto complete of ab
ab
abcd
abx
abyz
--------------------------------
true
true
false
https://ideone.com/nCu5aH
language:
C++ (gcc 8.3)
created:
9 days 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!