MYCODES/Tries.cpp at master · ashishugi/MYCODES · GitHub

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
class TrieTree {
    public:
    char ch;
    bool isEnd;
    TrieTree* child[26];
    TrieTree (){
        isEnd = false;
        for(int i=0;i<26;i++) {
            this->child[i] = NULL;
        }
    }
};
class Trie {
public:
    TrieTree* head;
    Trie() {
        head = new TrieTree();
    }

    void insert(string word) {
        TrieTree* curr = head;
        for(int i=0;i<word.length();i++) {
            int index = word[i] - 'a';
            if(curr->child[index]) {
                // if this exist
                curr = curr->child[index];
            } else {
                // this does not exist
                TrieTree* temp = new TrieTree();
                curr->child[index] = temp;
                temp->isEnd = false;
                temp->ch = word[i];
                curr = curr->child[index];
            }
        }
        curr->isEnd = true;
    }

    bool search(string word) {
        TrieTree* curr = head;
        for(int i=0;i<word.length();i++) {
            int index = word[i]-'a';
            if(curr->child[index]) {
                // if this exist
                curr = curr->child[index];
            } else {
               return false;
            }
        }
        if(curr->isEnd) {
            return true;
        }
        return false;
    }

    bool startsWith(string prefix) {
         TrieTree* curr = head;
        for(int i=0;i<prefix.length();i++) {
            int index = prefix[i]-'a';
            if(curr->child[index]) {
                // if this exist
                curr = curr->child[index];
            } else {
               return false;
            }
        }
        return true;
    }
};