【数据结构与算法】【LeetCode】【动态规划】139.单词拆分

dp数组，记忆化数组

题目

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

说明：

• 拆分时可以重复使用字典中的单词。
• 你可以假设字典中没有重复的单词。

示例 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. 初始化 $dp=[False,\cdots,False]$，长度为 n+1。n 为字符串长度。$dp[i]$ 表示 s 的前 i 位是否可以用 wordDict中的单词表示。

2. 初始化 $dp[0]=True$，空字符可以被表示。

3. 遍历字符串的所有子串，遍历开始索引 i，遍历区间$ [0,n)$：

   • 遍历结束索引 j，遍历区间 $[i+1,n+1)$：
     • 若 $dp[i]=True$且 $s[i,\cdots,j)$ 在 wordlist 中：$dp[j]=True$

       解释：$dp[i]=True$说明s 的前 i位可以用 wordDict 表示，则$ s[i,\cdots,j)$出现在 wordDict 中，说明 s 的前 j位可以表示。

4. 返回 $dp[n]$

复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def wordBreak(self, s: str, wordDict) -> bool:
        n=len(s)
        dp=[False]*(n+1) # 初始化n+1个false
        dp[0]=True            # 空字符可以被表示
        for i in range(n):
            for j in range(i+1,n+1):
                if dp[i] and s[i:j] in wordDict:
                    dp[j]=True
        #print(dp)
        return dp[-1]

1
2
3
4
5

a= Solution()
s = "leetcode"
wordDict = ["leet", "code"]
result=a.wordBreak(s,wordDict)
print(result)

True

1
2
3
4
5

a= Solution()
s = "applepenapple"
wordDict = ["apple", "pen"]
result=a.wordBreak(s,wordDict)
print(result)

True

1
2
3
4
5

a= Solution()
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
result=a.wordBreak(s,wordDict)
print(result)

[True, False, False, True, True, False, False, True, False, False]
False

方法二：记忆化回溯

1. 使用记忆化函数，保存出现过的 backtrack(s)，避免重复计算。
2. 定义回溯函数 backtrack(s)

• 若 s 长度为 0，则返回 True，表示已经使用 wordDict中的单词分割完。
• 初始化当前字符串是否可以被分割 res=False
• 遍历结束索引 i，遍历区间 [1,n+1)：
  • 若 $s[0,\cdots,i-1]$在 wordDict中：$res=backtrack(s[i,\cdots,n-1])\ or\ res$。

    解释：保存遍历结束索引中，可以使字符串切割完成的情况。

• 返回 resres

3. 返回 backtrack(s)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def wordBreak(self, s: str, wordDict) -> bool:
        import functools
        @functools.lru_cache(None)
        def back_track(s):
            if(not s):
                return True
            res=False
            for i in range(1,len(s)+1):
                if(s[:i] in wordDict):
                    res=back_track(s[i:]) or res
            return res
        return back_track(s)

a= Solution()
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
result=a.wordBreak(s,wordDict)
print(result)

False