之前写过一篇关于 Trie 树的实现：使用Trie 树实现搜索引擎的搜索关键词提示功能，现在我们来使用 Java 再来重新实现一下，随后做几道习题来玩玩。
代码实现前缀树
https://leetcode-cn.com/problems/implement-trie-prefix-tree/
/**
* @Date: 2022-03-13 14:17
* @Author: liushengxi
* @Description:
*/
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
// [0,1,2,3,4,5,6,7,8,9,10]
// 数组下标表示 字符-`a` 的值
isEnd = false;
}
public void insert(String word) {
// node 刚开始指向的是 trie 的 树根，以后依次向下指向，所以最后其 isEnd = true
Trie node = this;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
// 注意 isEnd 都是 false
node.children[index] = new Trie();
}
// 如果还是空，先创建，再移动 node 指针
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = helperSearchPrefix(word);
// 这里指针已经指向了 search 的最后一个字符，所以直接判断是否是结束字符即可。
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return helperSearchPrefix(prefix) != null;
}
private Trie helperSearchPrefix(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;
}
public static void main(String[] args) {
Trie obj = new Trie();
obj.insert("hello");
System.out.println(obj.search("hello"));
System.out.println(obj.search("hell"));
System.out.println(obj.search("helloa"));
System.out.println(obj.startsWith("hell"));
System.out.println(obj.startsWith("helloa"));
System.out.println(obj.startsWith("hello"));
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_2 = obj.search(word);
*/
- 时间： O(∣S∣)，其中 |S|是每次插入或查询的字符串的长度。
- 空间：O(∣T∣⋅Σ)，其中∣T∣ 为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26。
212. 单词搜索 II
https://leetcode-cn.com/problems/word-search-ii/
思路：
class Solution {
int[][] dirs = {
{
1, 0}, {
-1, 0}, {
0, 1}, {
0, -1}};
public List<String> findWords(char[][] board, String[] words) {
Test.Trie trie = new Test.Trie();
for (String word : words) {
trie.insert(word);
}
Set<String> ans = new HashSet<String>();
for (int i = 0; i < board.length; ++i) {
for (int j = 0; j < board[0].length; ++j) {
dfs(board, trie, i, j, ans);
}
}
return new ArrayList<String>(ans);
}
public void dfs(char[][] board, Test.Trie now, int i, int j, Set<String> ans) {
if (!now.children.containsKey(board[i][j])) {
return;
}
char ch = board[i][j];
now = now.children.get(ch);
if (!"".equals(now.word)) {
ans.add(now.word);
}
// 表示已访问过
board[i][j] = '#';
for (int[] dir : dirs) {
int xx = i + dir[0], yy = j + dir[1];
if (xx >= 0 && xx < board.length && yy >= 0 && yy < board[0].length) {
dfs(board, now, xx, yy, ans);
}
}
// 回溯时，恢复状态
board[i][j] = ch;
}
}
class Trie {
String word;
Map<Character, Test.Trie> children;
public Trie() {
this.word = "";
this.children = new HashMap<Character, Test.Trie>();
}
public void insert(String word) {
Test.Trie cur = this;
for (int i = 0; i < word.length(); ++i) {
char ch = word.charAt(i);
if (!cur.children.containsKey(ch)) {
cur.children.put(ch, new Test.Trie());
}
cur = cur.children.get(ch);
}
// word 保存最终的单词,其余 trie树 上面为空
cur.word = word;
}
}
剑指 Offer II 063. 替换单词
思路：
//输入：dictionary=["cat","bat","rat"],
// sentence="the cattle was rattled by the battery"
// 输出："the cat was rat by the bat"
class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
StringBuilder result = new StringBuilder();
//Set 去做
Set<String> stringSet = new HashSet<>(dictionary);
for (String retval : sentence.split(" ")) {
// StringBuilder 没有 StringBuilder(char ch) 的构造函数
StringBuilder sb = new StringBuilder(String.valueOf(retval.charAt(0)));
for (int i = 1; i < retval.length(); i++) {
if (stringSet.contains(sb.toString())) {
retval = sb.toString();
break;
} else {
sb.append(retval.charAt(i));
}
}
result.append(retval);
result.append(" ");
}
return result.substring(0, result.length() - 1);
}
}