Leetcode.208.Implement Trie (Pre

题目

自定义一个树，实现树的插入字符串， 查找字符串， 是否有包含前缀的字符串。
字符串只包含a-z。

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

思路1

使用set。插入和查找都有系统方法。判断前缀通过二分法查找，效率还是太低。

class Trie {
public:
    set<string> m_set;
    /** Initialize your data structure here. */
    Trie() {

    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        m_set.insert(word);
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        return m_set.count(word) > 0;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        vector<string> vec(m_set.begin(), m_set.end());
        int l = 0, r = (int)vec.size()-1;
        while (l <= r) {
            int mid = (l + r) / 2;
            string s = vec[mid];
            if (s.substr(0,prefix.size()) == prefix) {
                return true;
            }else if (s.substr(0,prefix.size()) > prefix) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return false;
    }
};

思路2

由于只包含a~z的字符，所以可以建立一个26维的数结构，分支都是a~z的字符，通过一个结束标识符判断是否是一个完整的字符串。
挺巧妙的一种设计结构，适合查找前缀这种场景。

class Trie {
public:
struct TrieNode {
    TrieNode *ch[26] = {nullptr};
    bool isEnd;
};

TrieNode *root = nullptr;

Trie() {
    root = new TrieNode();
}

void insert(string word) {
    TrieNode *temp = root;
    for (char c : word) {
        if (temp->ch[c-'a'] == nullptr) {
            temp->ch[c-'a'] = new TrieNode();
        }
        temp = temp->ch[c-'a'];
    }
    temp->isEnd = true;
}

bool search(string word) {
    TrieNode *temp = root;
    for(char c : word) {
        if (temp->ch[c-'a'] == nullptr) {
            return false;
        }
        temp = temp->ch[c-'a'];
    }
    return temp->isEnd;
}

bool startsWith(string prefix) {
    TrieNode *temp = root;
    for(char c : prefix) {
        if (temp->ch[c-'a'] == nullptr) {
            return false;
        }
        temp = temp->ch[c-'a'];
    }
    return true;
}
};

总结

n维树的实现，学习了多维树的使用。