问题描述

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

辅助数组 d[] 中的第 i 个分量表示子串 s[0 ... i] 能否被拆分为一个或多个在字典中出现的单词。状态转移方程是：

• 如果 i 等于 0，那么 d[i] 等于 s[i] 是否在 wordDict 中
• 对于任意 j（0 <= j <= i - 1），如果 d[j] 为 true，并且 s[j+1 ... i+1] 在 wordDict 中，那么 d[i] 等于 true
• d[i] 等于 s[0 ... i] 是否在 wordDict 中

最终，d 中的最后一个元素就是要求的结果。

Python 实现

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        wordDict = set(wordDict)
        d = [False for _ in range(len(s))]
        for i in range(len(s)):
            if i == 0:
                d[i] = s[i] in wordDict
                continue
            j = i - 1
            while j >= 0:
                if d[j] and s[j+1: i+1] in wordDict:
                    d[i] = True
                    break
                j = j - 1
            else:
                d[i] = s[:i+1] in wordDict
        return d[-1]