单词查找树

发表于 | 分类于 | 阅读次数:
字数统计: 521 | 阅读时长 ≈ 2

《算法(第4版)》5.2节讲到了单词查找树(也就是字典树)，这里结合LeetCode相关题目进行分析。

LeetCode描述：

Implement a trie with insert, search, and startsWith methods.
You may assume that all inputs are consist of lowercase letters a-z.

这里用26个字母代替原书中ASCII扩展字符，要求实现insert、search and startsWith方法。

构造Node

TrieNode和普通Node最大区别是，添加了一个boolean字段，这个字段表示从根节点到当前节点命中一个已知字符串。

1
2
3
4
5
6
7
8
class TrieNode {
    public boolean bool;
    public TrieNode[] next;
    public TrieNode() {
      next = new TrieNode[26];
      bool = false;
    }
}

构造单词查找树(insert)

每一棵树都有一个大小为26的数组，将已知的字符串抽离成一个个字符，每个字符按先后顺序分别与’a’作差，每一个差值对应的就是当前树节点中数组的索引，数组索引位置指向的节点为空，就new，不为空，就以该节点出发继续遍历，遍历结束后，将当前节点的boolean值设为true：

1
2
3
4
5
6
7
8
9
10
11
12
public void insert(String word) {
  TrieNode p = root;
  for (int i = 0; i < word.lengh(); i++) {
    int index = word.charAt(i) - 'a';
    if (p.next[index] == null) {
      p.next[index] = new TrieNode();
    }
    root = p.next[index];
  }
  p.bool =true;
}

查找

查找和构造的区别在于，构造的时候没有就new，查找的时候没有就返回null，所以代码如下：

1
2
3
4
5
6
7
8
9
10
11
private TrieNode find(String s) {
    TrieNode p = root;
    for (int i = 0; i < s.length(); i++) {
        int index = s.charAt(i) - 'a';
        if (p.next[index] == null) {
            return null;
        }
        p = p.next[index];
    }
    return p;
}

搜索

搜索和查找的区别在于，搜索需要判断便利结束后当前node的bool值是否为true，所以代码如下：

1
2
3
4
public boolean search(String s) {
    TrieNode p = find(s);
    return p != null && p.bool;
}

startsWith

startsWith和搜索的区别在于，它不需要直到当前node的bool值是否为true：

1
2
3
4
public boolean startsWith(String s) {
    TrieNode p = find(s);
    return p != null;
}

小结

字典树用空间换取时间，搜索和构造的时间复杂度都是O(m)，m为最长字符串长度。空间成本最坏情况为RNm，R为字母表大小。