字典树

leetcode 208

class Trie {
  private Trie[] children;  // 对应 26个字母
  private boolean isEnd;    // 判断当前前缀是否是一个单词
  public Trie() {
      children = new Trie[26];
      isEnd = false;
  }
  public void insert(String word) {
      Trie node = this;
      for (int i = 0; i < word.length(); i++) {
          char ch = word.charAt(i);
          int index = ch - 'a';
          if (node.children[index] == null) {    // 建立下一层前缀树结点
              node.children[index] = new Trie();
          }
          node = node.children[index];
      }
      node.isEnd = true;
  }
  public boolean search(String word) {
      Trie node = searchPrefix(word);
      return node != null && node.isEnd;
  }
  public boolean startsWith(String prefix) {
      return searchPrefix(prefix) != null;
  }
  private Trie searchPrefix(String prefix) {
      Trie node = this;
      for (int i = 0; i < prefix.length(); i++) {
          char ch = prefix.charAt(i);
          int index = ch - 'a';
          if (node.children[index] == null) {
              return null;
          }
          node = node.children[index];
      }
      return node;
  }
}

leetcode 211 (利用 dfs 实现字典树的插入和查找，且适配通配符 ‘.’)

class Trie {
  Trie[] children;
  boolean isEnd; // 判断当前前缀是否是完整的单词
  Trie() {
      children = new Trie[26];
      isEnd = false;
  }
  private void helpBuild(String word, Trie node, int i, int n) {
      if(i == n) {  // 遍历字符串完成，插入成功
          node.isEnd = true;
          return;
      }
      if(word.charAt(i) == '.') {   // . 为通配符，可适配任何小写字母
          for(int k = 0; k < 26; k++) {
              if(node.children[k] == null) {
                  node.children[k] = new Trie();
              }
              helpBuild(word, node.children[k], i+1, n);
          }
      }else {
          int index = word.charAt(i) - 'a';
          if(node.children[index] == null) {
              node.children[index] = new Trie();
          }
          helpBuild(word, node.children[index], i+1, n);
      }
  }
  public void insert(String word) {
      if(word == null || word.length() == 0) {
          return;
      }
      Trie node = this;

      // 递归建立字典树
      helpBuild(word, node, 0, word.length());
  }
  private boolean helpSearch(String word, Trie node, int i, int n) {
      if(i == n) {
          return node.isEnd;
      }
      if(word.charAt(i) == '.') {  // 通配符
          boolean ans = false;
          for(int k = 0; k < 26; k++) {    // 在26个分支中，只要有1个匹配成功即可，不需要搜索所有情况
              if(node.children[k] != null) {
                  ans = ans || helpSearch(word, node.children[k], i+1, n);
                  if(ans == true) {
                      return true;
                  }
              }
          }
          return ans;
      }else {
          int index = word.charAt(i) - 'a';
          if(node.children[index] == null) {
              return false;
          }
          else {
              return helpSearch(word, node.children[index], i+1, n);
          }
      }
      //return false;
  }
  public boolean search(String word) {
      Trie node = this;
      return helpSearch(word, node, 0, word.length());
  }
}
class WordDictionary {
  Trie trie;

  public WordDictionary() {
      trie = new Trie();
  }

  public void addWord(String word) {
      trie.insert(word);
  }

  public boolean search(String word) {
      return trie.search(word);
  }
}