我们现在有个需求,如何判断一堆不重复的字符串是否以某个前缀开头
可以用
Set/Map
存储字符串(保证字符串不重复)
- 遍历所有的字符串进行判断
- 时间复杂度
O(n)
有没有更优的数据结构来实现前缀搜索呢?
我们可以使用Trie前缀树
我们常常在路由中使用前缀树这一数据结构,用来匹配/api/:id
这样的路由
Trie的优点:搜索前缀的效率主要跟前缀的长度有关
Trie的缺点:浪费内存
更多Trie的数据结构和算法有:Double-array Trie(DAT)、Suffix Tree(后缀树)、Patricia Tree(Radix Trie 或 Compact Trie)、Crit-bit Tree (二进制位压缩树)、AC自动机
- Trie也叫字典树、前缀树(prefix Tree)、单词查找树
- Trie搜索字符串的效率主要跟字符串的长度有关
假设使用
Trie
存储cat、dog、doggy、does、cast、add六个单词
// 接口设计1
int size();
boolean isEmpty();
void clear();
boolean contains(String str);
void add(String str);
void remove(String str);
boolean starsWith(String prefix);
// 接口设计2
int size();
boolean isEmpty();
void clear();
boolean contains(String str);
V get(String key);
V add(String str, V value);
V remove(String str);
boolean starsWith(String prefix);
第一套接口很像set
,第二套接口很像map
package com.fx.trie;
import java.util.HashMap;
import java.util.Map;
/**
* <p>
*
* </p>
*
* @author 梁峰源 <fengyuan-liang@foxmail.com>
* @since 2023/6/24 14:25
*/
public class Trie<V> implements ITrie<V> {
private static class Node<V> {
Map<Character, Node<V>> children; // 存储分叉的子结点,k为当前节点存储的字符
V value;
boolean isEndWord; // 是否以单词的结尾(是否为一个完整的单词)
public Map<Character, Node<V>> getChildren() {
return children == null ? (children = new HashMap<>()) : children;
}
}
private int size;
private final Node<V> root = new Node<>();
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public void clear() {
size = 0;
root.children.clear();
}
@Override
public boolean contains(String str) {
return false;
}
@Override
public V get(String key) {
Node<V> node = node(key);
return node == null ? null : node.value;
}
@Override
public V add(String k, V value) {
keyCheck(k);
Node<V> node = root;
for (char c : k.toCharArray()) {
Node<V> childNode = node.getChildren().get(c);
if (childNode == null) {
childNode = new Node<>();
node.getChildren().put(c, childNode);
}
node = childNode;
}
// 之前没有单词
if (!node.isEndWord) {
node.isEndWord = true; node.value = value; size++;
return null;
}
// 存在则覆盖
V oldValue = node.value;
node.value = value;
return oldValue;
}
@Override
public V remove(String str) {
Node<V> node = node(str);
if (node == null) {
return null;
}
node.isEndWord = false;
V oldValue = node.value;
node.value = null;
return oldValue;
}
@Override
public boolean starsWith(String prefix) {
keyCheck(prefix);
Node<V> node = root;
for (char c : prefix.toCharArray()) {
node = node.getChildren().get(c);
if (node == null) {
return false;
}
}
return true;
}
private Node<V> node(String key) {
keyCheck(key);
Node<V> node = this.root;
int len = key.length();
for (int i = 0; i < len; i++) {
char c = key.charAt(i); // d o g
node = node.getChildren().get(c);
if (node == null) {
return null;
}
}
return node.isEndWord ? node : null;
}
private void keyCheck(String key) {
if (key == null || key.length() == 0) {
throw new IllegalArgumentException("key is empty");
}
}
}