139. 单词拆分

发表于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 6 分钟

做算法题，不紧张是不可能的 —— Charles

给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。

说明：拆分时可以重复使用字典中的单词。

示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

提示：
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同

  1. 单词拆分 —— 传送门

题目如上，我没有都贴出来，省略了两个例子，太长了，凑合看吧。意思就是给你一个字符串集合，看看能不能刚好用集合中的词拼出给定的字符串。

解这道题目，我的想法还是先穷举，无论任何题目，其实都是穷举法，你首先要想出至少一种的穷举办法。当然你想出来的未必是最终用的方法，但是你至少想出一种。有了一个正确的穷举，你才可以谈论如何在上面优化。

这个题目让人迷惑在什么地方，我们可以用一个单词来分割这个字符串，例如，我们用 a 将 bab 这个串分割为两个 b，如果 b 在给定的字典里，那么就是可以拆分。但是因为目标串里的字母可以重复，所以，word 出现的边界不好确定，如果选错了边界，就会导致两侧不能继续被拆分。

这里其实有个问题，就是我们为什么会想到从中间拆分这个串呢？因为我们是按顺序遍历字典的。所以，字典里的第一个串，不一定出现在目标串的哪个位置。更一般的，我们会想到是从中间的某个地方去分割这个串。其实这是一个误区，因为从中间将串分为两截，前后两截也并不好处理，而且中间的位置，这个中间也是模糊的。

简化的想法其实是控制一头，我们总是去掉一个前缀，或者去掉一个后缀，如果剩下和还能用原来的字典拆分，则整个串可以被拆分。如果选错了前后缀，我们就换一个。这么一来，这就成了一个显然的递归算法。我们把目标串能否拆分，替换了目标串的前后缀能否拆分这样一个子问题。

1
2
3
4
5
6
7
8
9
10
11
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    n = len(s)
    def dfs(st: int):
        if st == n: return True
        
        for w in wordDict:
            if s.startswith(w, st):
                res = dfs(st + len(w))
                if res: return True
        return False
    return dfs(0)

设计一个递归算法的方法，其实就是假设我们已经设计出了这个算法。

假设，我们得到了一个算法，这个算法可以判定目标串从 st 开始的后缀能不能被字典拆分。显然，从 len(s) 也就是目标串的长度开始的后缀，长度是 0 ，一定是可以被拆分的。剩下，我们只要遍历字典，去掉一个以字典中的词前缀后，用递归方法判定后缀就可以了。

如果是高手很容易看出来，我当时设计算法的时候，不是用上述的想法，上述的想法是我后来编的。当然，能直接这么想出来，也没什么不自然。我设计算法的时候，是用另一个方法，就是回溯法，而回溯法和 dfs 又往往是千丝万缕，当然不完全是一回事，不过写多了就喜欢这么命名了。

从回溯法出发的思路也可以解释一下，就是从目标串的 st 下标开始搜索，如果可以成功扩展一个前缀，就深入一层，从 st + len(word) 这个下标开始，用相同的方法继续向前探索，如果探索失败就回退到 st，如果探索成功就直接返回。听起来是不是也有点像深度优先搜索呢？所以我总喜欢用 dfs 来命名回溯的方法名。

结合题目的规模提示，我们可以分析一下这个算法的时间复杂度，递归的每一层，分支数量是字典的长度 m，单词的长度是 n，时间复杂度是 O(m^n)，不超过 1000^300也就是 10^900。这是一个天文数字。当然，因为字典里每个词都是不同的，所以实际拆分没那么恐怖，但是你不用侥幸，肯定在那个量级。

考虑到我们设计的这个算法很很巧妙，只有一个标量参数，也就是开始下标。而且，显然这个 st 是会被重复访问到的。比如 babccc 这个目标串，测试字典是 [a, b, ba, ab, c]，其前缀 bab，对应字典前几个词，可以有多种方法，所以，显然 ccc 这个后缀会反复被搜索到，所以如果我们缓存了后，就会大量节省搜索时间。我可以用 st 作 key，缓存计算结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    n = len(s)

    @cache   #注意这里
    def dfs(st: int):
        if st == n: return True
        
        for w in wordDict:
            if s.startswith(w, st):
                res = dfs(st + len(w))
                if res: return True
        return False
    return dfs(0)

Python 就是这么变态，只要在方法名前面加个修饰 @cache 就可以了，这个方法的值会自动调用 lru_cache。如此，就不会超时了（TLE）。加过缓存后，这个算法的时间复杂度就会大幅下降，目标串的每个 st 下标位置会缓存一个结果。然后就是对字典的遍历。

这道题目还可以用动态规划来解。因为我们发现，这个题目满足重叠子问题，最优子结构，无后效性三个条件。重叠子问题是，每个前缀后缀会被反复判定。最优子结构是，我们只需要回答能否被拆分，而不需要回答拆分的方法是什么。无后效性是，一个前后缀的拆分，跟已经切割掉的前后缀无关。

转移方程是这样的：f(n) = f(n - len(w)) && “w 是一个合法前后缀”

如果一个单词 w 是这个串的合法前后缀，那么去掉这个单词前后缀后，剩下的长度还是可以拆分，则说明整个串可以拆分，回到原初，一个空串显然是可以拆分的。基于上述分析，得到算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    n = len(s)

    dp = [False] * (n + 1)
    dp[0] = True

    for i in range(1, n + 1):
        for w in wordDict:
            if dp[i] : break
            if i - len(w) >= 0:
                dp[i] = dp[i - len(w)] and s.endswith(w, 0, i)
    return dp[n]

这个算法的时间复杂度是O(mn)，m是字典长度，n 是目标串长度。空间复杂度是 O(n)。

— END —