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. ~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
stdin
Trie homework 2
stdout
all strings in the trie
a
ab
abcd
abx
abyz
bcd
xyz
--------------------------------
auto complete of ab
ab
abcd
abx
abyz
--------------------------------
true
true
false