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.     vector<string>myWords;
  15.     ~Trie() {
  16.         for (int i = 0; i < chars; i++) {
  17.             if (child[i]) {
  18.                 delete child[i];
  19.             }
  20.         }
  21.     }
  22.  
  23.     void insert(const string& s, int idx = 0) {
  24.         if (idx == s.length()) {
  25.             isLeaf = true;
  26.         } else {
  27.             int cur = s[idx] - 'a';
  28.             if (child[cur] == nullptr) {
  29.                 child[cur] = new Trie();
  30.             }
  31.             child[cur]->insert(s, idx + 1);
  32.         }
  33.         myWords.push_back(s);
  34.     }
  35.  
  36.  
  37.     vector<string> autoComplete(const string &s){
  38.         vector<string>ans;
  39.         for(auto w : myWords){
  40.             if(w.substr(0,s.length()) == s){
  41.                 ans.push_back(w);
  42.             }
  43.         }
  44.         sort(ans.begin(), ans.end());
  45.         return ans;
  46.     }
  47. };
  48.  
  49. int main() {
  50.     Trie tree;
  51.     tree.insert("abcd");
  52.     tree.insert("ab");
  53.     tree.insert("abx");
  54.     tree.insert("abyz");
  55.     tree.insert("xyz");
  56.     tree.insert("a");
  57.     tree.insert("bcd");
  58.     vector<string>res;
  59.     res = tree.autoComplete("ab");
  60.  
  61.     for(auto &str:res){
  62.         cout<<str<<endl;
  63.     }
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ab
abcd
abx
abyz
https://ideone.com/yuxBUF
language:
C++ (gcc 8.3)
created:
8 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!