python实现leetcode之140. 单词拆分 II

解题思路

动态规划
dp[i]表示到i为止有哪些切分方式

140. 单词拆分 II

代码

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        N = len(s)
        wordDict = set(wordDict)
        # dp[i]表示到i为止有哪些切分方式
        dp = [[] for _ in range(N+1)]
        for i in range(N+1):
            for j in range(i):
                if s[j:i] in wordDict:
                    if j == 0:
                        dp[i].append([s[j:i]])
                    else:
                        for item in dp[j]:
                            dp[i].append([*item, s[j:i]])
        return [' '.join(item) for item in dp[N]]