FilesExpand file tree

 main

/

implement_trie.cpp

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

74 lines (54 loc) · 1.43 KB

 main

/

implement_trie.cpp

Top

File metadata and controls

• Code
• Blame

74 lines (54 loc) · 1.43 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

class TrieNode{

public:

TrieNode* children[26];

bool isEnd;

TrieNode(){

isEnd = false;

for(int i = 0; i < 26; i++)

children[i] = nullptr;

}

};

class Trie {

public:

TrieNode* root;

Trie() {

root = new TrieNode();

}

void insert(string word) {

TrieNode* node = root;

for(int i = 0; i < word.length(); i++){

int idx = word[i] - 'a';

if(!node->children[idx])

node->children[idx] = new TrieNode();

node = node->children[idx];

}

node->isEnd = true;

}

bool search(string word) {

TrieNode* node = root;

for(int i = 0; i < word.length(); i++){

int idx = word[i] - 'a';

if(!node->children[idx])

return false;

node = node->children[idx];

}

return node->isEnd;

}

bool startsWith(string prefix) {

TrieNode* node = root;

for(int i = 0; i < prefix.length(); i++){

int idx = prefix[i] - 'a';

if(!node->children[idx])

return false;

node = node->children[idx];

}

return true;

}

};

/**

* Your Trie object will be instantiated and called as such:

* Trie* obj = new Trie();

* obj->insert(word);

* bool param_2 = obj->search(word);

* bool param_3 = obj->startsWith(prefix);

*/