[139][中等][DFS] 单词拆分

题目描述

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

解题思路

从第一个字符开始, 逐步增加字符组成更长的前缀串, 如果前缀子串是一个单词, 那么我们继续判断去掉这个前缀剩余的子串是否也能被拆分成多个单词, 这里就看出了DFS的思路. 如果子串也可以被拆分成多个单词, 那么整体符合, 返回True, 如果子串不可以, 则继续扩大前缀子串, 寻找是否可以组成更长的单词, 直到遇到下一个单词, 再重复上述的步骤.

因此整体来看是一个标准的DFS过程. 定义递归结束的边界, 即下潜的子串长度为0, 说明已经遍历了所有的字符, 且整体已经被拆分成多个单词了.

如果逐步扩大前缀串, 直到前缀串完全等于字符串, 还是不相等, 继续扩大就会发生越界. 因此越界的时候返回False.

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

        @lru_cache(None)
        def dfs(substring):
            n = len(substring)
            if n == 0:
                return True

            i = 0
            while i < n:
                if substring[:i + 1] in dic and dfs(substring[i + 1:]):
                    return True
                i += 1
            return False

        return dfs(s)