139. 单词拆分 #

问题描述#

给定一个非空字符串 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

解题思路#

首先，常规的做法就是使用递归。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if s in wordDict:
            return True

        for i in range(len(s)):
            if s[: i + 1] in wordDict:
                if self.wordBreak(s[i + 1 :], wordDict):
                    return True
        return False

结果超时。

因为在递归时，对一些状态会进行反复计算，一个技巧是可以考虑使用 Python functools 库中的装饰器 lru_cache，因为 lru_cache 需要参数是可 hash 的，所以不能直接在原函数 wordBreak 加上 @lru_cache，可以在函数内部重新定义一个函数。代码如下：

from functools import lru_cache
from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        len_s = len(s)

        @lru_cache
        def f(k: int) -> bool:
            if k == len_s:
                return True

            for i in range(k, len_s):
                if s[k : i + 1] in word_set and f(i + 1):
                    return True

            return False

        return f(0)

我们也可以不使用 lru_cache，而是自定义一个变量来保存某个状态是否满足要求，一旦该状态不满足要求，我们将其记录下来，下次遇到这个状态，直接返回即可。代码如下：

from collections import defaultdict
from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        len_s = len(s)
        v = defaultdict(lambda: True)

        def f(k: int) -> bool:
            if not v[k]:
                return False

            if k == len_s:
                return True

            for i in range(k, len_s):
                if s[k : i + 1] in word_set and f(i + 1):
                    return True

            v[k] = False

            return False

        return f(0)

递归是通过不断减小问题规模，也可以通过使用动态规划来不断增加问题规模实现。代码如下：

from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (1 + n)
        dp[0] = True

        word_set = set(wordDict)
        for i in range(n):
            for j in range(i, -1, -1):
                if dp[j] and s[j : i + 1] in word_set:
                    dp[i + 1] = True
                    break

        return dp[-1]

在到达当前位置字符时，之前的所有字符串是否满足要求都已经被记录在 dp 数组中，第 12 和第 13 行的代码有不同的写法。

第 12 的代码也可以写为 for j in range(i + 1)，这样 s[j : i + 1] 的长度是由长到短，如果字典里的单词都比较短的话， s[j : i + 1] in word_set 就会一直为 False。这时我们可以将第 13 的代码改为 if s[j : i + 1] in word_set and dp[j]，即将两个条件交换一下顺序，但是显然判断 s[j : i + 1] in word_set 要比 dp[j] 耗时，所以第 13 行代码应该始终写为 if dp[j] and s[j : i + 1] in word_set。

for i in range(n):
    for j in range(i + 1):
        if dp[j] and s[j : i + 1] in word_set:
            dp[i + 1] = True
            break

for i in range(n):
    for j in range(i + 1):
        if s[j : i + 1] in word_set and dp[j]:
            dp[i + 1] = True
            break

for i in range(n):
    for j in range(i, -1, -1):
        if s[j : i + 1] in word_set and dp[j]:
            dp[i + 1] = True
            break

for i in range(n):
    for j in range(i, -1, -1):
        if dp[j] and s[j : i + 1] in word_set:
            dp[i + 1] = True
            break

139. 单词拆分#

问题描述#

解题思路#

139. 单词拆分 #