leetcode 211. Design Add and Search Words Data Structure | 211. 添加与搜索单词 - 数据结构设计（Java）

川长思鸟来 2022-10-06 12:57 56阅读 0赞

## 题目 ##

[https://leetcode.com/problems/design-add-and-search-words-data-structure/][https_leetcode.com_problems_design-add-and-search-words-data-structure]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

字典树 + 深度优先搜素，思路参考 [leetcode 208. Implement Trie (Prefix Tree) | 208. 实现 Trie 前缀树（Java）][leetcode 208. Implement Trie _Prefix Tree_ _ 208. _ Trie _Java]

class Node { 
        Node[] map;
        boolean isEnd;
    
        public Node() { 
            this.map = new Node['z' - 'a' + 1];
        }
    
        public Node get(char c) { 
    // System.out.printf("c=" + c);
            return map[c - 'a'];
        }
    
        public Node put(char c) { 
            Node node = new Node();
            map[c - 'a'] = node;
            return node;
        }
    }
    
    class WordDictionary { 
        Node node;
    
        public WordDictionary() { 
            node = new Node();
        }
    
        public void addWord(String word) { 
            char[] array = word.toCharArray();
            Node cur = node;
            for (int i = 0; i < array.length; i++) { 
                if (cur.get(array[i]) != null)
                    cur = cur.get(array[i]);
                else
                    cur = cur.put(array[i]);
                if (i == array.length - 1)
                    cur.isEnd = true;
            }
        }
    
        public boolean search(String word) { 
            return searchTrie(word, 0, node);
        }
    
        public boolean searchTrie(String word, int curIndex, Node lastNode) {  // 注意区分cur和last
            char[] array = word.toCharArray();
            if (curIndex == array.length || lastNode == null) return false; // curIndex或者lastNode越界
            if (curIndex + 1 == array.length && array[curIndex] != '.')  // word已经搜索到结尾 则递归返回
                return lastNode.get(array[curIndex]) != null && lastNode.get(array[curIndex]).isEnd;
    
            if (array[curIndex] == '.') { 
                for (Node curNode : lastNode.map) { 
                    if (curIndex + 1 == array.length && curNode != null && curNode.isEnd) return true; // 以.结尾
                    if (searchTrie(word, curIndex + 1, curNode)) return true; // dfs
                }
            } else return searchTrie(word, curIndex + 1, lastNode.get(array[curIndex])); // 普通字典树
            return false;
        }
    }
    
    /** * Your WordDictionary object will be instantiated and called as such: * WordDictionary obj = new WordDictionary(); * obj.addWord(word); * boolean param_2 = obj.search(word); */

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_design-add-and-search-words-data-structure]: https://leetcode.com/problems/design-add-and-search-words-data-structure/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/39bac9a6eff1438b9aa8f084b4aeb069.png
[leetcode 208. Implement Trie _Prefix Tree_ _ 208. _ Trie _Java]: https://hanquan.blog.csdn.net/article/details/117767824
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/5bedd063e96747fab7b295d4fe235800.png