华为 OD 训练营 · 题解精讲

LC139. 单词拆分

题目描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。

注意，你可以重复使用字典中的单词。

示例 3：输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false

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

题目解析

注意，本题为海康威视2024年9月12日秋招笔试真题

我们想知道最终的s是否能由wordDict中的单词构成。

一个容易想到的思路是，假设我们已经知道以索引i-1为结尾的子字符串s[:i]已经能够通过某些单词组合来构成（不管组成的细节），而接下来的s[i:j]是wordDict中一个已经存在的单词（存在i<j），那么这个以索引j-1为结尾的子字符串s[:j]可以通过s[:i] + s[i:j]来得到。

这俨然是一个动态转移方程的雏形。思考动态规划三部曲。

dp数组的含义是什么？构建长度为n+1的dp数组，令dp[i]的取值为True或者False，表示以索引i-1为结尾的子字符串s[:i]是否能够由wordDict中的若干单词构成。 n = len(s) # 获得字符串s的长度n dp = [False] * (n+1) # 构建一维dp数组，长度为(n+1)

dp[i]表示以索引i-1对应字符为结尾的子字符串s[0:i]能否由wordDict中的单词构成

dp[n]表示以索引n-1对应字符为结尾的子字符串s[0:n]也就是s，能否由wordDict中的单词构成

动态转移方程是什么？考虑前提dp[i] = True，表示s[:i]已经可以由wordDict中的若干单词构成。接下来我们寻找下一个可能延长的子字符s[i:j]，因此需要接下来遍历j的范围为i+1到n。如果发现s[i:j]是wordDict中的某一个单词，我们认为s[:j]可以通过原先的s[:i]加上s[i:j]去得到。此时可以把dp[j]修改为True，核心的动态转移方程即为 if dp[i] == True and s[i:j] in wordSet: dp[j] = True

加上循环即为

遍历以i-1为结尾索引的每一个子字符串s[:i]

for i in range(n+1):

剪枝，如果以索引i-1为结尾的字符串s[0:i]无法取到

则无需继续考虑剩余字符串s[i:n]

if dp[i] == False: continue

如果以索引i-1为结尾的字符串s[0:i]可以取到

则继续考虑后续的字符串结束索引j

for j in range(i+1, n+1):

如果接下来存在某个子字符串s[i:j]是已经存在的单词

则说明以索引j-1为结尾的子字符串s[:j]可以通过s[:i]+s[i:j]得到

将dp[j]修改为True

if s[i:j] in wordSet: dp[j] = True

dp数组如何初始化？空串""无需选取任何单词来拼接都可以得到，正如一个空袋子的状态无需选择任何物品装入都可以得到。因此dp[0]表示的空串状态s[:0] = ""我们直接设置为dp[0] = True作为整个dp过程的初始状态。

另外，需要注意的一点是，题目所给定的wordDict是以数组的形式呈现的，为了达成多次进行切片s[i:j]快速查找的目的，我们可以将其转化为集合，即wordSet = set(wordDict)。

实际上，本题也可以认为是一道路径依赖的完全背包问题。其中，最终要组成的字符串s为背包，而单词集wordDict为物品。

因此在代码中我们可以看到，我们先对背包进行了正序遍历，再对不限数目的物品进行了正序遍历。这跟我们在2023/07/07 真题讲解（动态规划背包问题专题）中的分析是完全一致的。

image.png

参考代码

class Solution:
    # 139题单词拆分 ：路径依赖的完全背包dp
    def wordBreak(self, s: str, wordDict: List[str]) -> bool: 
        # 把wordDict转为哈希集合，减少查找的时间复杂度
        wordSet = set(wordDict)
        n = len(s)              # 获得字符串s的长度n
        dp = [False] * (n+1)    # 构建一维dp数组，长度为(n+1)
        # dp[i]表示以索引i-1对应字符为结尾的子字符串s[0:i]能否由wordDict中的单词构成
        # dp[n]表示以索引n-1对应字符为结尾的子字符串s[0:n]也就是s，能否由wordDict中的单词构成
        # 初始化dp[0]为True，表示空串''总是可以通过不选择任何单词取到
        dp[0] = True
        
        # 遍历以i-1为结尾索引的每一个子字符串s[:i]
        for i in range(n+1):      
            # 剪枝，如果以索引i-1为结尾的字符串s[0:i]无法取到
            # 则无需继续考虑剩余字符串s[i:n]
            if dp[i] == False:
                continue
            # 如果以索引i-1为结尾的字符串s[0:i]可以取到
            # 则继续考虑后续的字符串结束索引j
            for j in range(i+1, n+1):
                # 如果接下来存在某个子字符串s[i:j]是已经存在的单词
                # 则说明以索引j-1为结尾的子字符串s[:j]可以通过s[:i]+s[i:j]得到
                # 将dp[j]修改为True
                if s[i:j] in wordSet:
                    dp[j] = True
        # 最后返回dp[n]是否为True
        return dp[-1]

← 上一篇

LC135. 分发糖果

LC150. 逆波兰表达式求值