华为OD技术面一，手撕题正好遇到不太熟悉的前缀树。总体思路是想到了，
但是一些细节还是没有考虑到，比如：
- 想到用字典模拟树结构，但是没想到用嵌套字典，导致构造前缀树的
复杂度没有降下来。
- 想到要建立前缀树，但是还想在建树的同时进行连接词的判断，导致
建树的复杂度上升，有更多的细节问题需要考虑。应该将建树和判断连接词
分别考虑，遍历两次，这样既不需要按单词长度进行排序这步预操作，在代码
实现上也容易得多。
- 想到要对单词进行连接词判断，但是没有想到用递归的方式，和前两个欠
考虑之处有点关系。
- 一旦采用递归来判断连接词，那么各种优化操作也更容易实现，比如：
- 维护已知为连接词的单词集合，加速未处理单词的判断过程。
题目
描述：给你一个不含重复单词的字符串数组 words，请你找出并返回 words
中的所有连接词。
连接词：一个完全由给定数组中的至少两个较短单词组成的字符串。
提示：
1 <= words.length <= 1040 <= words[i].length <= 1000words[i] 仅由小写字母组成0 <= sum(words[i].length) <= 105
样例：
输入：words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]
输出：["catsdogcats", "dogcatsdog", "ratcatdogcat"]
解释：
"catsdogcats" 由 "cats"，"dog" 和 "cats" 组成；
"dogcatsdog" 由 "dog"，"cats" 和 "dog" 组成；
"ratcatdogcat" 由 "rat"，"cat"，"dog" 和 "cat" 组成；
思路
遍历两次给定数组，第一遍构造前缀树，第二遍寻找连接词。
- 构造前缀树：用嵌套字典模拟树结构，用列表保存节点属性：嵌套字典表示的子树和
布尔值标识当前节点是否为单词结尾。
- 寻找连接词：递归回溯查找。
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#!/usr/bin/env python
def insert(strees, s):
"""
构建字符串的前缀树，用嵌套字典表示树结构，列表存储节点属性。
strees: {u: [{}, True/False]}
"""
d = strees
for c in s[:-1]:
if c not in d:
d[c] = [{}, False]
d = d[c][0]
c = s[-1]
if c not in d:
d[c] = [{}, False]
d[c][1] = True
def search(strees, s, count, visited):
"""
回溯算法
s: 待判断是否为连接词的子串
count: 当前分割的单词集合
visited: 当前判定为连接词的单词集合
"""
# 如果先前判定过 s 为连接词，则直接返回
if s in visited:
return 2
d = strees
for i, c in enumerate(s[:-1]):
if c not in d:
# 一定在递归调用过程中，否则 c 必在 d 中。
# 上一步分割无解，返回 0
return 0
if d[c][1]:
# 尝试在下标 i 处分割
count.add(s[: i + 1])
remain = search(strees, s[i + 1 :], count, visited)
# 剪枝
if remain < 2:
# 下标 i 处作分割无解，寻找下一个分割点
count.remove(s[: i + 1])
d = d[c][0]
else:
# 分割成功，不需要找出所有方案，直接返回
return remain
else:
d = d[c][0]
c = s[-1]
if c in d and d[c][1]:
count.add(s)
return len(count)
else:
# 意味着 s 无法匹配
return 0
def getConnectedString(arr):
"""
arr: [word1, ...]
"""
strees = {}
for word in arr:
insert(strees, word)
ans = set()
for word in arr:
count = search(strees, word, set(), ans)
if count >= 2:
ans.add(word)
return list(ans)
|
泛福轩