leetcode [139] 单词拆分

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定一个非空字符串 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 == '': return False
        memo = [None] * len(s)
        self.wordBreakCore(s, 0, wordDict, memo)
        return False if memo[-1] is None else memo[-1]

    def wordBreakCore(self, s: str, start, wordDict, memo) -> bool:
        if start >= len(s):
            return True
        if memo[start] != None:
            return memo[start]
        for i in range(start, len(s)):
            if s[start: i + 1] in wordDict and self.wordBreakCore(s, i + 1, wordDict, memo):
                memo[i] = True
                return True
        memo[start] = False
        return False