fork download
copy 
  1. #include <iostream>
  2. #include <string.h>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. struct trie {
  8. 	bool word = false;
  9. 	trie* adj[26];
  10. 	trie() {
  11. 		for (int i = 0; i < 26; i++) adj[i] = NULL;
  12. 	}
  13.  
  14. 	void add(char* s) {
  15. 		trie* t = this;
  16.  
  17. 		while (*s) {
  18. 			if (t->adj[s[0] - 'a'] == NULL) {
  19. 				trie* novaPtr = create(s + 1);
  20. 				t->adj[s[0] - 'a'] = novaPtr;
  21. 				return;
  22. 			}
  23. 			else {
  24. 				t = t->adj[s[0] - 'a'];
  25. 			}
  26. 			s++;
  27. 		}
  28. 	}
  29.  
  30. 	trie* create(char* s) {
  31. 		trie *t = new trie();
  32. 		trie* point = t;
  33. 		while (*s) {
  34. 			point->adj[s[0] - 'a'] = new trie(); // allocate memory on heap
  35. 			point = point->adj[s[0] - 'a'];
  36. 			s++;
  37. 		}
  38. 		point->word = true;
  39. 		return t; // the pointer on heap memeroy is returned.
  40. 	}
  41.  
  42. 	void seek() {
  43. 		trie* t = this;
  44. 		run(t, "");
  45. 	}
  46.  
  47. 	void run(trie* t, string s) {
  48. 		if (t->word) {
  49. 			cout << s << "\n";
  50. 		}
  51. 		for (int i = 0; i < 26; i++) {
  52. 			if (t->adj[i] != NULL) {
  53. 				run(t->adj[i], s + char('a' + i));
  54. 			}
  55. 		}
  56. 	}
  57. };
  58.  
  59. int main() {
  60. 	trie t;
  61. 	t.add("ball");
  62. 	t.seek();
  63. 	t.add("balloon");
  64. 	t.add("cluster");
  65. 	t.seek();
  66. }
  67.  
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
ball
ball
balloon
cluster
https://ideone.com/XpL5nb
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!