fork download 
  1. #include <iostream>
  2. #include <string>
  3. #include <iomanip>
  4. #include <memory>
  5. #include <ios>
  6.  
  7. class Trie
  8. {
  9. private:
  10.  
  11. 	std::unique_ptr<Trie> nodes[26] = {};
  12.  
  13. public:
  14.  
  15. 	/** Initialize your data structure here. */
  16. 	Trie() = default;
  17.  
  18. 	/** Inserts a word into the trie. */
  19. 	void insert(std::string const &word)
  20. 	{
  21. 		Trie *current = this;
  22. 		for (auto c : word)
  23. 		{
  24. 			int i = c - 'a';
  25.  
  26. 			if (!current->nodes[i])
  27. 				current->nodes[i] = std::make_unique<Trie>();
  28.  
  29. 			current = current->nodes[i].get();
  30. 		}
  31. 	}
  32.  
  33. 	/** Returns if the word is in the trie. */
  34. 	bool search(std::string const &word)
  35. 	{
  36. 		Trie *current = this;
  37. 		for (auto c : word)
  38. 		{
  39. 			int i = c - 'a';
  40.  
  41. 			if (!current->nodes[i])
  42. 				return false;
  43.  
  44. 			current = current->nodes[i].get();
  45. 		}
  46.  
  47. 		return true;
  48. 	}
  49.  
  50. 	/** Returns if there is any word in the trie that starts with the given prefix. */
  51. 	bool startsWith(std::string const &prefix) 
  52. 	{
  53. 		return search(prefix);
  54. 	}
  55.  
  56. 	/**
  57. 	* Your Trie object will be instantiated and called as such:
  58. 	* Trie obj = Trie();
  59. 	* obj.insert(word);
  60. 	* bool param_2 = obj.search(word);
  61. 	* bool param_3 = obj.startsWith(prefix);
  62. 	*/
  63.  
  64. };
  65.  
  66. int main()
  67. {
  68. 	Trie obj = Trie();
  69. 	obj.insert("fuck");
  70.  
  71. 	std::cout << "The word \"fcuk\" is found: " << std::boolalpha << obj.search("fcuk") << std::endl;
  72. 	std::cout << "The word \"fuck\" is found: " << std::boolalpha << obj.search("fuck") << std::endl;
  73. 	std::cout << "A word with \"fc\" prefix exists: " << std::boolalpha << obj.startsWith("fc") << std::endl;
  74. 	std::cout << "A word with \"fu\" prefix exists: " << std::boolalpha << obj.startsWith("fu") << std::endl;
  75.  
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 4304KB
comments (?)
stdin 
Standard input is empty
stdout 
The word "fcuk" is found: false
The word "fuck" is found: true
A word with "fc" prefix exists: false
A word with "fu" prefix exists: true
https://ideone.com/95x2ne
language:
C++14 (gcc 8.3)
created:
7 years 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!