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

  1. class WordDictionary {
  2.     class TrieNode {
  3.         public TrieNode[] children;
  4.         public boolean isEnd = false;
  6.         public TrieNode() {
  7.             children = new TrieNode[26];
  8.             isEnd = false;
  9.         }
  10.     } 
  12.     TrieNode root;
  13.     /** Initialize your data structure here. */
  14.     public WordDictionary() {
  15.         root = new TrieNode();
  16.     }
  18.     public void addWord(String word) {
  19.         if (word == null || word.length() == 0)
  20.             return ;
  22.         TrieNode node = root;
  24.         char[] chs = word.toCharArray();
  25.         for (char ch : chs) {
  26.             if (node.children[ch - 'a'] == null)
  27.                 node.children[ch - 'a'] = new TrieNode();
  29.             node = node.children[ch - 'a'];
  30.         }
  32.         node.isEnd = true;
  33.     }
  35.     public boolean search(String word) {
  36.         return dfs(word, root, 0);
  37.     }
  39.     private boolean dfs(String word, TrieNode node, int start) {
  40.         if (start == word.length())
  41.             return node.isEnd;
  43.         char ch = word.charAt(start);
  44.         if (ch != '.') {
  45.             if (node.children[ch - 'a'] == null)
  46.                 return false;
  48.             return dfs(word, node.children[ch - 'a'], start + 1);
  49.         } else {
  50.             int index = 0;
  51.             for (index = 0; index < 26; index++) {
  52.                 // 递归遍历node节点后面的所有路径
  53.                 if (node.children[index] != null && dfs(word, node.children[index], start + 1))
  54.                     return true;
  55.             }
  56.             return false;
  57.         }
  58.     }
  59. }
  61. /**
  62.  * Your WordDictionary object will be instantiated and called as such:
  63.  * WordDictionary obj = new WordDictionary();
  64.  * obj.addWord(word);
  65.  * boolean param_2 = obj.search(word);
  66.  */