网站的分辨率是多少,安徽网络公司排名,与网站设计相关的软件主要有,wordpress评论开关文章目录 一、题目二、思路三、代码 一、题目 二、思路
具体例子和步骤#xff1a;假设 s aab#xff0c;步骤如下#xff1a; 初始状态#xff1a; s aabpath []res [] 第一层递归#xff08;外层循环#xff09;#xff1a; path []检… 文章目录 一、题目二、思路三、代码 一、题目 二、思路
具体例子和步骤假设 s aab步骤如下 初始状态 s aabpath []res [] 第一层递归外层循环 path []检查 s[:1] 即 a是回文 递归调用 dfs(ab, [a], res) 第二层递归 s abpath [a]检查 s[:1] 即 a是回文 递归调用 dfs(b, [a, a], res) 第三层递归 s bpath [a, a]检查 s[:1] 即 b是回文 递归调用 dfs(, [a, a, b], res) 终止条件 s path [a, a, b]res 加入 path即 res [[a, a, b]] 回溯并尝试新的分割 回溯至 s abpath [a]检查 s[:2] 即 ab不是回文跳过。回溯至初始状态s aabpath []检查 s[:2] 即 aa是回文 递归调用 dfs(b, [aa], res) 新的递归路径 s bpath [aa]检查 s[:1] 即 b是回文 递归调用 dfs(, [aa, b], res) 终止条件 s path [aa, b]res 加入 path即 res [[a, a, b], [aa, b]]
Initial call: dfs(aab, [])
|
|-- dfs(ab, [a])
| |
| |-- dfs(b, [a, a])
| | |
| | |-- dfs(, [a, a, b]) -- Add to result [[a, a, b]]
| |
| -- dfs(b, [a]) -- ab 不是回文跳过
|
-- dfs(b, [aa])||-- dfs(, [aa, b]) -- Add to result [[a, a, b], [aa, b]]代码逻辑
for i in range(1, len(s) 1)循环从1开始到 len(s)尝试每一个可能的分割位置。if self.isP(s[:i])检查从0到 i 的子串 s[:i] 是否是回文。self.dfs(s[i:], path [s[:i]], res)如果 s[:i] 是回文将 s[:i] 添加到路径 path 中递归处理剩余的字符串 s[i:]。
每次递归调用会传递新的字符串 s 和更新后的路径 path这个路径即当前方案的所有字符组合列表直到字符串 s 为空此时将路径 path 添加到结果列表 res 中。这样通过递归和回溯的方法我们可以找到所有可能的分割方案。递归调用部分
for i in range(1, len(s) 1):if self.isP(s[:i]):self.dfs(s[i:], path [s[:i]], res)s[:i]表示从字符串 s 的第1个字符到第 i 个字符形成的子串。path [s[:i]]表示将当前找到的回文子串 s[:i] 添加到当前的 path 中形成一个新的列表。
三、代码
class Solution(object):def partition(self, s)::type s: str:rtype: List[List[str]]res []self.dfs(s, [], res)return res def dfs(self, s, path, res):s: 剩余的字符串path: 当前分割方案res: 保存所有分割方案的结果if not s:res.append(path)return for i in range(1, len(s) 1):if self.isP(s[:i]):self.dfs(s[i:], path[s[:i]], res)def isP(self, s):return s s[::-1]
