word break

image

这个代码框架是很典型的DP框架
当前的dp[i]去往前寻找合适的状态

def wordBreak(self, s, wordDict):
    """
    :type s: str
    :type wordDict: List[str]
    :rtype: bool
    """
    if not s or not wordDict:
        return False
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(len(s)):  # 现在的index针对s所以dp的index需要+1
        for j in range(i, -1, -1):
            if s[j:i + 1] in wordDict and dp[j]:
                dp[i + 1] = True
                break
    # print(dp)
    return dp[-1]

重点是第二题

要求给出所有的拆分方法

image

对于这种问题 很容易想到的是DFS搜索出所有路径

def wordBreak(self, s, wordDict):
    """
    :type s: str
    :type wordDict: List[str]
    :rtype: List[str]
    """
    if not self.helper(s, wordDict):
        return []
    res = []
    def DFS(s, path):
        if not s:
            res.append(path)
            return
        for w in wordDict:
            if s[:len(w)] == w:
                DFS(s[len(w):], path + [w])
    DFS(s, [])
    res = [" ".join(x) for x in res]
    return res

优化成记忆

def wordBreak_memo(self, s, wordDict):
    """
    :type s: str
    :type wordDict: List[str]
    :rtype: List[str]
    """
    # res = []
    memo = {}
    def DFS(s):
        if s in memo:
            return memo[s]
        if not s: # 因为不是不匹配 其实是匹配的 这里已经到了终止条件了 所以返回一个空串
            return [""]
        res = [] # 初始化成[] 因为默认是没有路径 如果有了 再往里加就完事
        for w in wordDict:
            if s[:len(w)] == w: # 我们会担心 当前w满足了 如果后面不匹配 后面D
                # 按照现在的写法
                for path in DFS(s[len(w):]):
                    if path:
                        res.append(w + " " + path)
                    else:
                        res.append(w) # 因为此时已经到头了 s中没有多余字符
                # res += [w + (" " if path else "") + path
        memo[s] = res
        return res
    return DFS(s)

这里DFS return 的两种情况

• [] 没有可行的拆分方法
• [""] 递归终止条件

看一下dp解法

def wordBreak_DP(self, s, wordDict):
    if not s or not wordDict:
        return False
    dp = [[] for _ in range(len(s) + 1)]
    dp[0] = [""]  # dp[i] 是一个list list中每一个元素是一个字符串
    for i in range(len(s)):
        for j in range(-1, i):
            if s[j + 1:i + 1] in wordDict and len(dp[j + 1]):
                dp[i + 1] += [path + (" " if path else "") + s[j + 1:i + 1] for path in dp[j + 1]]  # 让path是字符串
    return dp[-1]

会内存爆炸