LeetCode問題解(127):Implement Trie(Prefix Tree)

タイトル:
Implement a trie with insert , search , and startsWith methods.
Note: You may assume that all inputs are consist of lowercase letters a-z . 問題:
純データ構造.
C++版:

class TrieNode {
public:
    // Initialize your data structure here.
    bool leaf;
    TrieNode* children[26];
    TrieNode() {
        leaf = false;
        for(int i = 0; i< 26; i++)
            children[i] = NULL;
    }
};

class Trie {
public:

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

    // Inserts a word into the trie.
    void insert(string word) {
        if(word.length() == 0)
            return;
        TrieNode* p = root;
        for(int i = 0; i < word.length(); i++) {
            if(p->children[word[i] - 'a'] == NULL) {
                TrieNode* newNode = new TrieNode();
                p->children[word[i] - 'a'] = newNode;
            }
            p = p->children[word[i] - 'a'];
            if(i == word.length() - 1)
                p->leaf = true;
        }
    }

    // Returns if the word is in the trie.
    bool search(string word) {
        if(word.length() == 0)
            return false;
        TrieNode* p = root;    
        for(int i = 0; i < word.length(); i++) {
            if(p->children[word[i] - 'a'] == NULL)
                return false;
            p = p->children[word[i] - 'a'];
            if(i == word.length() - 1 && p->leaf)
                return true;
        }
        return false;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        if(prefix.length() == 0)
            return false;
        TrieNode* p = root;    
        for(int i = 0; i < prefix.length(); i++) {
            if(p->children[prefix[i] - 'a'] == NULL)
                return false;
            p = p->children[prefix[i] - 'a'];
        }
        return true;
    }

private:
    TrieNode* root;
};

// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");

Java版:

class TrieNode {
    // Initialize your data structure here.
    public boolean leaf;
    public TrieNode[] children;
    
    public TrieNode() {
        leaf = false;
        children = new TrieNode[26];
    }
}

public class Trie {
    private TrieNode root;

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

    // Inserts a word into the trie.
    public void insert(String word) {
        if(word.length() == 0)
            return;
            
        TrieNode p = root;    
        for(int i = 0; i < word.length(); i++) {
            if(p.children[word.charAt(i) - 'a'] == null) {
                TrieNode newNode = new TrieNode();
                p.children[word.charAt(i) - 'a'] = newNode;
            }
            p = p.children[word.charAt(i) - 'a'];
            if(i == word.length() - 1)
                p.leaf = true;
        }
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        if(word.length() == 0)
            return false;
            
        TrieNode p = root;    
        for(int i = 0; i < word.length(); i++) {
            if(p.children[word.charAt(i) - 'a'] == null)
                return false;
            p = p.children[word.charAt(i) - 'a'];
            if(i == word.length() - 1 && p.leaf)
                return true;
        }
        return false;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        if(prefix.length() == 0)
            return false;
            
        TrieNode p = root;    
        for(int i = 0; i < prefix.length(); i++) {
            if(p.children[prefix.charAt(i) - 'a'] == null)
                return false;
            p = p.children[prefix.charAt(i) - 'a'];
        }
        return true;        
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");

Python版:

class TrieNode:
    # Initialize your data structure here.
    def __init__(self):
        self.leaf = False
        self.children = [None] * 26

class Trie:

    def __init__(self):
        self.root = TrieNode()

    # @param {string} word
    # @return {void}
    # Inserts a word into the trie.
    def insert(self, word):
        if len(word) == 0:
            return
        
        p = self.root
        for i in range(len(word)):
            if p.children[ord(word[i]) - ord('a')] == None:
                q = TrieNode()
                p.children[ord(word[i]) - ord('a')] = q
            p = p.children[ord(word[i]) - ord('a')]
            if i == len(word) - 1:
                p.leaf = True

    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the trie.
    def search(self, word):
        if len(word) == 0:
            return False
        
        p = self.root
        for i in range(len(word)):
            if p.children[ord(word[i]) - ord('a')] == None:
                return False
            p = p.children[ord(word[i]) - ord('a')]
            if i == len(word) - 1 and p.leaf:
                return True
        return False

    # @param {string} prefix
    # @return {boolean}
    # Returns if there is any word in the trie
    # that starts with the given prefix.
    def startsWith(self, prefix):
        if len(prefix) == 0:
            return False
        
        p = self.root
        for i in range(len(prefix)):
            if p.children[ord(prefix[i]) - ord('a')] == None:
                return False
            p = p.children[ord(prefix[i]) - ord('a')]
        return True        

# Your Trie object will be instantiated and called as such:
# trie = Trie()
# trie.insert("somestring")
# trie.search("key")