140. 单词拆分 II

题目链接

解题思路：和139题类似，只不过要把所有的结果存起来而已

代码

class Solution:

    def check(self, s: str, i: int, s2: str) -> int:
        if i + len(s2) > len(s):
            return -1
        for ch in s2:
            if ch != s[i]:
                return -1
            i += 1
        return i

    # 现在在凑s[index...]，能凑出来吗？
    def process(self, s: str, index: int, wordDict: List[str], ans: List[str], res: str) -> None:
        if index == len(s):
            ans.append(res)
            return 
        # 用哪个字符来凑？
        for str1 in wordDict:
            next_index = self.check(s, index, str1)
            if next_index != -1:
                add_count = 0
                if len(res) == 0:
                    res += str1
                    add_count = len(str1)
                else:
                    res += ' '
                    res += str1
                    add_count = len(str1) + 1
                self.process(s, next_index, wordDict, ans, res)
                # 恢复现场
                res = res[:-add_count]

    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        ans = []
        res = ""
        self.process(s, 0, wordDict, ans, res)
        return ans