LintCode 442. Implement Trie 原创Java参考解答

LintCode 442. Implement Trie 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/implement-trie/

Implement a trie with insert, search, and startsWith methods.

Example

insert("lintcode")
search("code")
>>> false
startsWith("lint")
>>> true
startsWith("linterror")
>>> false
insert("linterror")
search("lintcode)
>>> true
startsWith("linterror")
>>> true

解题思路

题目是考察Trie字典树的实现。

理解字典树的结构,就会很容易用代码实现字典树。字典树每个结点TrieNode都有个长度大小为26的TrieNode数组和表示是否是单词的boolean变量hasWord。Trie的基本操作包括insert、search、startWith。

参考代码

/** 
 * Your Trie object will be instantiated and called as such: 
 * Trie trie = new Trie(); 
 * trie.insert("lintcode"); 
 * trie.search("lint"); will return false 
 * trie.startsWith("lint"); will return true 
 */ 
class TrieNode { 
    public TrieNode[] children; 
    public boolean hasWord; 
    // Initialize your data structure here. 
    public TrieNode() { 
        this.children = new TrieNode[26]; 
        this.hasWord = false; 
    } 
} 
 
public class Trie { 
    private TrieNode root; 
 
    public Trie() { 
        root = new TrieNode(); 
    } 
 
    // Inserts a word into the trie. 
    public void insert(String word) { 
        TrieNode p = root; 
        for (int i = 0; i < word.length(); i++) { 
            int c = word.charAt(i) - 'a'; 
            if (p.children[c] == null) { 
                p.children[c] = new TrieNode(); 
            } 
            p = p.children[c]; 
        } 
        p.hasWord = true; 
    } 
 
    // Returns if the word is in the trie. 
    public boolean search(String word) { 
        TrieNode p = root; 
        for (int i = 0; i < word.length(); i++) { 
            int c = word.charAt(i) - 'a'; 
            if (p.children[c] == null) { 
                return false; 
            } 
            p = p.children[c]; 
        } 
        return p.hasWord;         
    } 
 
    // Returns if there is any word in the trie 
    // that starts with the given prefix. 
    public boolean startsWith(String prefix) { 
        TrieNode p = root; 
        for (int i = 0; i < prefix.length(); i++) { 
            int c = prefix.charAt(i) - 'a'; 
            if (p.children[c] == null) { 
                return false; 
            } 
            p = p.children[c]; 
        } 
        return true;       
    } 
}

相关题目

LintCode All in One 原创题目讲解汇总

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注