208. Implement Trie (Prefix Tree)

刷
June-20-2019

白给的。

时间复杂度都和str的长度有关。这个结构其实就是空间换时间

class Trie {
    
    public class Node {
        boolean isLetter;
        Character letter;
        Map<Character, Node> nextLevel;
        
        public Node(Character letter, boolean isLetter) {
            this.isLetter = isLetter;
            this.letter = letter;
            this.nextLevel = new HashMap<>();
        }
    }
    
    
    Node root;
    

    /** Initialize your data structure here. */
    public Trie() {
        this.root = new Node(null, false);
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node temp = root;
        for (Character c : word.toCharArray()) {
            if (!temp.nextLevel.containsKey(c)) {
                temp.nextLevel.put(c, new Node(c, false));
            }
            temp = temp.nextLevel.get(c);
        }
        temp.isLetter = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node temp = root;
        for (Character c : word.toCharArray()) {
            if (!temp.nextLevel.containsKey(c)) {
                return false;
            } else {
                temp = temp.nextLevel.get(c);
            }
        }
        return temp.isLetter;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Node temp = root;
        for (Character c : prefix.toCharArray()) {
            if (!temp.nextLevel.containsKey(c)) {
                return false;
            } else {
                temp = temp.nextLevel.get(c);
            }
        }
        return (temp.isLetter || !temp.nextLevel.isEmpty());
    }
}

Node[26] 来做也行.

nextLevel[tempChar - 'a'] = new Node()这样