131.Palindrome Partitioning

方法一：输入的视角（逗号选或不选）假设每对相邻字符之间有个逗号，那么就看每个逗号是选还是不选。

也可以理解成：是否要在 i 和 i+1 处分割，把 s[i] 作为当前子串的最后一个字符，把 s[i+1] 作为下一个子串的第一个字符。

注意 s[n−1] 一定是最后一个字符，所以在 i=n−1 的时候一定要分割。

python

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        ans = []
        path = []

        # 考虑 i 后面的逗号怎么选
        # start 表示当前这段回文子串的开始位置
        def dfs(i: int, start: int) -> None:
            if i == n:  # s 分割完毕
                ans.append(path.copy())  # 复制 path
                return

            # 不分割，不选 i 和 i+1 之间的逗号
            if i < n - 1:  # i=n-1 时只能分割
                # 考虑 i+1 后面的逗号怎么选
                dfs(i + 1, start)

            # 分割，选 i 和 i+1 之间的逗号（把 s[i] 作为子串的最后一个字符）
            t = s[start: i + 1]
            if t == t[::-1]:  # 判断是否回文
                path.append(t)
                # 考虑 i+1 后面的逗号怎么选
                # start=i+1 表示下一个子串从 i+1 开始
                dfs(i + 1, i + 1)
                path.pop()  # 恢复现场

        dfs(0, 0)
        return ans

作者：灵茶山艾府
链接：https://leetcode.cn/problems/palindrome-partitioning/solutions/2059414/hui-su-bu-hui-xie-tao-lu-zai-ci-pythonja-fues/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

My solution

python

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        ans = []
        path = []
        def dfs(i: int, start: int):
            if i == n:
                ans.append(path[::])
                return
            # not choose
            if i < n - 1:
                dfs(i+1, start)
            # choose
            sub = s[start: i+1]
            if sub == sub[::-1]:
                path.append(sub)
                dfs(i+1, i+1)
                path.pop()

        dfs(0, 0)
        return ans

方法二：答案的视角（枚举子串结束位置）

python

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        ans = []
        path = []
        def dfs(start: int):
            if start == n:
                ans.append(path[::])
                return
            for end in range(start, n):
                substring = s[start:end+1]
                if substring == substring[::-1]:
                    path.append(substring)
                    # 考虑剩余的 s[j+1:] 怎么分割
                    dfs(end+1)
                    path.pop()
        dfs(0)
        return ans