字典树 04 Leetcode中的211号问题

211. 添加与搜索单词 - 数据结构设计

• 查看Trie中是否存在单词word，从操作过程看，就是依次拿出word的每个字母，去Trie中与其对应的层中查找，而这一层的节点所表示的字母并不存储在该层的节点中，而是存储在该层父节点的边（父节点映射的key，父节点映射的value就是该层的节点）中，这层的节点中只存储指向其的边是否是一个单词的终点；
• 从递归的角度看就是：在Trie的节点node中，查看是否存在边word.charAt(index)，字典树中的边就是字母，其实就是在一个节点上找一个字母，找到了就在下一个节点找下一个字母；
• 递归问题都可以分成2部分：规模更小的同一个问题和不能再缩小的基本为题；进入规模更小的同一个问题是有条件的，只有满足这个条件了才能进入规模更小的基本问题；进入了规模更小的同一个问题就相当于是进入了递归链，只有沿着递归链前进下去才能到规模更小的同一个问题；
• 随着问题的复杂，进入递归链的入口也会不止一个，本问题就有2个进入递归链的入口，即 c != '.' 和 c == '.'，这2个入口进入的递归链是平行的；
• 来到递归链的入口后，想要真正进入递归链也是有约束的，这个约束和简单的只有1个递归链入口的问题是一样的；
• 本问题首先要看出问题的可递归性，然后分2种情况，由2个递归入口进入递归链；

import java.util.TreeMap;

public class WordDictionary {

    private class Node{

        public boolean isWord;
        public TreeMap<Character, Node> next;

        public Node(boolean isWord){
            this.isWord = isWord;
            next = new TreeMap<>();
        }

        public Node(){
            this(false);
        }
    }

    private Node root;

    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new Node();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {

        Node cur = root;
        for(int i = 0 ; i < word.length() ; i ++){
            char c = word.charAt(i);
            if(cur.next.get(c) == null)
                cur.next.put(c, new Node());
            cur = cur.next.get(c);
        }
        cur.isWord = true;
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return match(root, word, 0);
    }

    private boolean match(Node node, String word, int index){

        if(index == word.length())
            return node.isWord;

        char c = word.charAt(index);

        if(c != '.'){
            if(node.next.get(c) == null)
                return false;
            return match(node.next.get(c), word, index + 1);
        }
        else{
            for(char nextChar: node.next.keySet())
                if(match(node.next.get(nextChar), word, index + 1))
                    return true;
            return false;
        }
    }
}