Leetcode 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

递归解法

以 wordBreak(s, wordDict) 作为判断字符串 s 可否拆分为 wordDict 的函数。则对于字符串 s 和下标 i，若 s[:i+1] 在 wordDict 中，如果 wordBreak(s[i+1:], wordDict) 返回 True，则表示字符串 s 可被拆分为 wordDict。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        if not s:
            return True
        for i in range(len(s)):
            if s[:i+1] in wordDict and self.wordBreak(s[i+1:],wordDict):
                return True
        return False

递归运算可能存在大量的重复计算，当字符串较大时可能会超时。

递归+存储中间值解法

以 wordMatch 存储字符串对应函数值。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordMatch,wordSet=dict(),set(wordDict)
        def breakCyc(s):
            if not s:
                return True
            for i in range(len(s)):
                if s[:i+1] in wordSet:
                    flag=wordMatch.get(s[i+1:],-1)
                    if flag==-1:
                        flag=breakCyc(s[i+1:])
                        wordMatch[s[i+1:]]=flag
                    if flag:
                        return True
            return False
        return breakCyc(s)

动态规划解法

以列表 arr 记录字符串 s 的每个可拆分前缀的下标，则从上一个前缀继续拓展遍历时，若当前的子字符串可拆分，则必然由前面的某一个可拆分前缀和 wordDict 中某个单词组成。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        arr,wordSet=[0],set(wordDict)
        for i in range(len(s)):
            for j in arr[::-1]:
                if s[j:i+1] in wordSet:
                    arr.append(i+1)
                    break
        return arr[-1]==len(s)