Commit1efba4d

authored

Create 208-Implement-Trie.cpp

C++ solution for 208-Implement-Trie

1 parent6f46719 commit1efba4dCopy full SHA for 1efba4d

File tree

+60

-0

lines changed

+60

-0

lines changed

Lines changed: 60 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,60 @@`
	`1`	`+structTrieNode {`
	`2`	`+TrieNode* children[26];`
	`3`	`+bool isWordEnd;`
	`4`	`+`
	`5`	`+TrieNode() : isWordEnd(false) {`
	`6`	`+for (int i =0; i <26; ++i)`
	`7`	`+children[i] =nullptr;`
	`8`	`+}`
	`9`	`+};`
	`10`	`+`
	`11`	`+classTrie {`
	`12`	`+private:`
	`13`	`+TrieNode* root;`
	`14`	`+public:`
	`15`	`+Trie() {`
	`16`	`+root =new TrieNode;`
	`17`	`+}`
	`18`	`+`
	`19`	`+voidinsert(string word) {`
	`20`	`+TrieNode* cur = root;`
	`21`	`+`
	`22`	`+int idx;`
	`23`	`+for (int i =0; i < word.size(); ++i) {`
	`24`	`+idx = word[i] -'a';`
	`25`	`+if (cur->children[idx] ==nullptr)`
	`26`	`+cur->children[idx] =new TrieNode;`
	`27`	`+cur = cur->children[idx];`
	`28`	`+}`
	`29`	`+// mark the last node as end of a word`
	`30`	`+cur->isWordEnd =true;`
	`31`	`+}`
	`32`	`+`
	`33`	`+boolsearch(string word) {`
	`34`	`+TrieNode* cur = root;`
	`35`	`+`
	`36`	`+int idx;`
	`37`	`+for (int i =0; i < word.size(); ++i) {`
	`38`	`+idx = word[i] -'a';`
	`39`	`+if (cur->children[idx] ==nullptr)`
	`40`	`+returnfalse;`
	`41`	`+cur = cur->children[idx];`
	`42`	`+}`
	`43`	`+// check if the node is end of any word`
	`44`	`+return cur->isWordEnd;`
	`45`	`+}`
	`46`	`+`
	`47`	`+boolstartsWith(string prefix) {`
	`48`	`+TrieNode* cur = root;`
	`49`	`+`
	`50`	`+int idx;`
	`51`	`+for (int i =0; i < prefix.size(); ++i) {`
	`52`	`+idx = prefix[i] -'a';`
	`53`	`+if (cur->children[idx] ==nullptr)`
	`54`	`+returnfalse;`
	`55`	`+cur = cur->children[idx];`
	`56`	`+}`
	`57`	`+// only need to check if the node exists`
	`58`	`+returntrue;`
	`59`	`+}`
	`60`	`+};`

Comments

(0)