fork download
  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
stdin
Standard input is empty
stdout
ab
abcd
abx
abyz