Trie/Trie.cpp at master · MyAUTDataStructureCourse/Trie · 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
//
// Created by ahmad on 12/16/16.
//

#include "Trie.h"
#include <algorithm>

TrieNode::TrieNode()
{
    for (int i = 0; i < MAX_ALPH; ++i) {
        children[i] = nullptr;
    }

    isWord = false;
}

Trie::Trie()
{
    this->root = new TrieNode;
}

void Trie::add(std::string word)
{
    // Making to the lower case
    std::transform(word.begin(), word.end(), word.begin(), ::tolower);

    TrieNode *pointer = this->root;

    int childIndex;

    for (int i = 0; i < word.size(); ++i) {
        childIndex = word.at(i) - 'a';
        if(!pointer->children[childIndex])
            pointer->children[childIndex] = new TrieNode;
        pointer = pointer->children[childIndex];
    }

    pointer->isWord = true;
}

bool Trie::isExisted(std::string word)
{
    // Making to the lower case
    std::transform(word.begin(), word.end(), word.begin(), ::tolower);

    TrieNode *pointer = this->root;

    int childIndex;

    for (int i = 0; i < word.size(); ++i) {
        childIndex = word.at(i) - 'a';
        if(pointer->children[childIndex])
            pointer = pointer->children[childIndex];
        else
            return false;
    }

    return pointer->isWord;
}