实现Trie

题目描述

实现一个 Trie，包含 insert, search, 和 startsWith 这三个方法。
例子：
insert(“lintcode”)
search(“code”) // return false
startsWith(“lint”) // return true
startsWith(“linterror”) // return false
insert(“linterror”)
search(“lintcode) // return true
startsWith(“linterror”) // return true

思路

单词查找树：
每个节点维护一个node[256]的数组
当前字符作为下标对应的node非空，所以每个单词都会形成一个链表
多个单词构成的链表组合起来，形成了单词查找树

代码

class TrieNode {
    // Initialize your data structure here.
    public TrieNode[] next;
    public boolean isWord;
    public TrieNode() { 
        next = new TrieNode[256];
        isWord = false;
    }
    public void addWord() {
        isWord = true;
    }
}

public class Trie {
    private TrieNode root;

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

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode tmp = root;
        for(int i = 0; i < word.length(); i++) {
            if(tmp.next[word.charAt(i)] == null) {
                tmp.next[word.charAt(i)] = new TrieNode();
            }
            tmp = tmp.next[word.charAt(i)];
        }
        tmp.addWord();
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        if(word.length() == 0) {
            return false;
        }
        TrieNode tmp = root;
        int i = 0;
        while(tmp != null && i != word.length()) {
            tmp = tmp.next[word.charAt(i)];
            i++;
        }
        if(i == word.length()) {
            if(tmp != null && tmp.isWord) {
                return true;
            }else {
                return false;
            }
        }else {
            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 true;
        }
        int i = 0;
        TrieNode tmp = root;
        while(tmp != null && i != prefix.length()) {
            tmp = tmp.next[prefix.charAt(i++)];
        }
        if(tmp == null) {
            return false;
        }else {
            return true;
        }
    }
}

考察点

• 字符串查找
• 单词查找树