题解 | #所有的回文子串I#

• 题目考察的知识点 : 递归回溯
• 题目解答方法的文字分析：

1. 定义一个函数isp(s, st, ed)来判断字符串s中从位置st到位置ed是否为回文串。然后，我们定义一个DFS函数dfs(s, u)来枚举以字符s[u]为起点的所有可能的回文串，并将其添加进当前回文串组path中。如果当前回文串组path包含了整个字符串s，则将其加入到结果列表res中。最后，我们从字符串s的第0个字符开始搜索，并返回所有回文串组的列表res。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return string字符串二维数组
#
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        path = []  # 定义用于保存当前回文串组的列表
        res = []  # 定义用于保存所有回文串组的列表

        # 判断字符串s1中从位置st到位置ed是否为回文串
        def isp(s1, st, ed):
            i, j = st, ed
            while i < j:
                if s1[i] != s1[j]:
                    return False
                i += 1
                j -= 1
            return True

        # 深度优先搜索函数，u表示当前在处理字符串s的第u个字符
        def dfs(s, u):
            nonlocal path, res
            if u >= len(s):  # 如果已经遍历完了整个字符串s，则说明找到了一组回文串组合
                res.append(path[:])  # 将当前回文串组加入到结果列表res中
                return
            for i in range(u, len(s)):  # 枚举以字符s[u]为起点的所有可能的回文串
                if isp(s, u, i):  # 如果s[u:i+1]是回文串，则将其添加进当前回文串组path中
                    str = s[u : i + 1]
                    path.append(str)
                else:
                    continue  # 如果s[u:i+1]不是回文串，则直接跳过
                dfs(s, i + 1)  # 递归处理字符串s中剩下的部分
                path.pop()  # 回溯，将刚才添加到path中的回文串移除

        dfs(s, 0)  # 从字符串s的第0个字符开始搜索
        return res  # 返回所有回文串组的列表res