fork download
copy 
  1. #include <iostream>
  2. #define ALPHABET_SIZE 26
  3. using namespace std;
  4.  
  5. struct TrieNode
  6. {
  7.     struct TrieNode *children[ALPHABET_SIZE];
  8.     bool isEndOfWord;
  9.     int elementCnt;
  10. };
  11.  
  12. class Trie {
  13. public:
  14.     /** Initialize your data structure here. */
  15.     struct TrieNode *head;
  16.  
  17.     Trie() {
  18.         head = getNode();
  19.     }
  20.  
  21.     TrieNode *getNode() { 
  22.         struct TrieNode *pNode =  new TrieNode; 
  23.  
  24.         pNode->isEndOfWord = false;
  25.         pNode->elementCnt = 0;
  26.  
  27.         for (int i = 0; i < ALPHABET_SIZE; i++)
  28.             pNode->children[i] = NULL;
  29.  
  30.         return pNode; 
  31.     } 
  32.  
  33.     /** Inserts a word into the trie. */
  34.     void insert(string word) {
  35.         struct TrieNode *temp = head;
  36.  
  37.         for(int i=0, idx; i < word.size(); ++i){
  38. 			idx = word[i]-'a';
  39.  
  40. 			if(!temp->children[idx]){
  41.                 temp->children[idx] = getNode();
  42. 				++temp->elementCnt;
  43. 			}
  44.  
  45.             temp = temp->children[idx];
  46.         }
  47.  
  48.         temp->isEndOfWord = true;
  49.     }
  50.  
  51.     /** Returns if the word is in the trie. */
  52.     bool search(string word) {
  53.         struct TrieNode *temp = head;
  54.  
  55.         for(int i=0, idx; i < word.size(); ++i){
  56. 			idx = word[i]-'a';
  57.  
  58.             if(!temp->children[idx])
  59.                 return false;
  60.  
  61.             temp = temp->children[idx];
  62.         }
  63.  
  64.         return temp && temp->isEndOfWord; 
  65.     }
  66.  
  67.     /** Returns if there is any word in the trie that starts with the given prefix. */
  68.     bool startsWith(string prefix) {
  69.         struct TrieNode *temp = head;
  70.  
  71.         for(int i=0; i < prefix.size(); ++i){
  72.             if(!temp->children[prefix[i]-'a'])
  73.                 return false;
  74.  
  75.             temp = temp->children[prefix[i]-'a'];
  76.         }
  77.  
  78.         return true;
  79.     }
  80.  
  81.     void commonPrefixes(struct TrieNode *rt){
  82.  
  83.         for(int i = 0; i < ALPHABET_SIZE; ++i){
  84.  
  85.             if(rt->children[i]){
  86. 	            cout<<(char)(i + 'a');
  87.  
  88. 	            bool flag = rt->children[i]->elementCnt > 1 ||
  89. 	            			rt->children[i]->isEndOfWord;
  90.  
  91. 	            if(flag){
  92. 	            	cout<<"\n";
  93. 	            	// return;
  94. 	            }
  95. 	            else{
  96. 	            	commonPrefixes(rt->children[i]);
  97. 	            }
  98.             }
  99.         }
  100.     }
  101.  
  102.     void printWords(struct TrieNode *temp, char *a, int k){
  103.  
  104.         if(temp->isEndOfWord){
  105.         	cout<<a<<"\n";
  106.         }
  107.  
  108.         for(int i=0; i<ALPHABET_SIZE; ++i){
  109.  
  110.             if(temp->children[i]){
  111.  
  112. 	            a[k] = i + 'a';
  113.  
  114. 	        	printWords(temp->children[i], a, k+1);
  115.  
  116. 				a[k+1] = '\0';
  117.             }
  118.         }
  119.     }
  120. };
  121.  
  122.  
  123. int main() {
  124. // 	ios::sync_with_stdio(0);
  125. // 	cin.tie(0);
  126.  
  127. 	int n; cin>>n;
  128. 	string inp;
  129.  
  130. 	Trie* obj = new Trie();
  131.  
  132. 	for(int i=0; i<n; ++i){
  133. 		cin>>inp;
  134. 		obj->insert(inp);
  135. 	}
  136.  
  137.  
  138. 	cout<<"Common prefixes:\n";
  139. 	obj->commonPrefixes(obj->head);
  140.  
  141. 	cout<<"*************************************************\n";
  142. 	cout<<"Words in Trie:\n";
  143.  
  144. 	char a[200];
  145. 	obj->printWords(obj->head, a, 0);
  146.  
  147. 	return 0;
  148. }
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
10
fought
flower
flow
nikki
nikku
nikko
nikkulu
yal
yalala
yali
stdout
copy 
Common prefixes:
f
nikk
yal
*************************************************
Words in Trie:
flow
flower
fought
nikki
nikko
nikku
nikkulu
yal
yalala
yali
https://ideone.com/e8ZWBO
Common Prefixes, sorted order of strings using prefix trie
language:
C++ (gcc 8.3)
created:
4 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!