fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <string>
  5. #include <unordered_map>
  6.  
  7. using namespace std;
  8. class Trie{
  9. 	public:
  10. 		vector<Trie*> child;
  11. 		unordered_map<int, int> umap; // Remaining characters -> # of words
  12.  
  13. 		Trie(){
  14. 			this->child.resize(128, nullptr);
  15. 		}
  16. 		void insertWord(string word){
  17. 			Trie *iter = this;
  18. 			for(int i = 0;i < word.size(); i++){
  19. 				int leftOver = word.size() - i;
  20. 				iter->umap[leftOver] += 1;
  21. 				if(iter->child[word[i]] == nullptr){
  22. 					iter->child[word[i]] = new Trie();
  23. 				}
  24. 				iter = iter->child[word[i]];
  25. 			}
  26. 			iter->umap[0] += 1;
  27. 		}
  28. 		int findWords(string word, int remLen){
  29. 			//cout << "\nword=" << word << " remlen=" << remLen << endl;
  30. 			Trie *iter = this;
  31. 			for(char c : word){
  32. 				iter = iter->child[c];
  33. 				if(iter == nullptr)
  34. 					return 0;
  35. 			}
  36. 			int numWord = iter->umap[remLen];
  37. 			//cout << "numWord=" << numWord << endl;
  38. 			return numWord;
  39. 		}
  40. 		bool findQuery(string word){
  41. 			string str = "";
  42. 			int remLen = 0;
  43. 			for(int i = 0;i < word.size(); i++){
  44. 				char c = word[i];
  45. 				if(isdigit(c)){
  46. 					while(i < word.size()){
  47. 						char c = word[i];
  48. 						if(!(isdigit(c)))
  49. 							break;
  50. 						remLen *= 10;
  51. 						remLen += (c - '0');
  52. 						i++;
  53. 					}
  54. 					break;
  55. 				} else {
  56. 					str += c;
  57. 				}
  58. 			}
  59. 			return this->findWords(str, remLen) == 1;
  60. 		}
  61. };
  62. class Solution{
  63. 	public:
  64. 		bool run_query(vector<string>& words, string query){
  65. 			Trie *trie = new Trie();
  66. 			for(string word : words){
  67. 				trie->insertWord(word);
  68. 			}
  69. 			return trie->findQuery(query);
  70. 		}
  71. };
  72. int main(){
  73. 	vector<string> words = {"ball", "cat", "baby", "cater"};
  74. 	cout << "words=";
  75. 	for(string word : words){
  76. 		cout << word << ",";
  77. 	}
  78. 	cout << endl;
  79. 	vector<string> all_queries = {"ca1", "cat", "ba2", "c4", "3", "4"};
  80. 	for(string query: all_queries){
  81. 		bool queryExists = Solution().run_query(words, query);
  82. 		cout << "query word=" << query << " unique exists=" << queryExists << endl;
  83. 	}
  84. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
words=ball,cat,baby,cater,
query word=ca1 unique exists=1
query word=cat unique exists=1
query word=ba2 unique exists=0
query word=c4 unique exists=1
query word=3 unique exists=1
query word=4 unique exists=0
https://ideone.com/NYaGQO
language:
C++14 (gcc 8.3)
created:
9 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!