记华为 OD 技术面一手撕题

泛福轩收录于类别算法面试

2024-03-11 2024-03-11 约 1089 字预计阅读 3 分钟次阅读条评论

注意

本文最后更新于 2024-03-11，文中内容可能已过时。

华为OD技术面一，手撕题正好遇到不太熟悉的前缀树。总体思路是想到了，但是一些细节还是没有考虑到，比如：

想到用字典模拟树结构，但是没想到用嵌套字典，导致构造前缀树的复杂度没有降下来。
想到要建立前缀树，但是还想在建树的同时进行连接词的判断，导致建树的复杂度上升，有更多的细节问题需要考虑。应该将建树和判断连接词 分别考虑，遍历两次，这样既不需要按单词长度进行排序这步预操作，在代码实现上也容易得多。
想到要对单词进行连接词判断，但是没有想到用递归的方式，和前两个欠考虑之处有点关系。
一旦采用递归来判断连接词，那么各种优化操作也更容易实现，比如：
- 维护已知为连接词的单词集合，加速未处理单词的判断过程。

题目

描述：给你一个不含重复单词的字符串数组 words，请你找出并返回 words 中的所有连接词。

连接词：一个完全由给定数组中的至少两个较短单词组成的字符串。

提示：

1 <= words.length <= 104
0 <= words[i].length <= 1000
words[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)

目录

记华为 OD 技术面一手撕题

题目

思路

解答

相关内容

目录

记华为 OD 技术面一手撕题

题目

思路

解答

相关内容

记快手笔试大题

记三七互娱笔试大题

记小米一面算法题——人民币大写金额转换