织梦医疗网站,下载app到手机上并安装,电子技术培训机构,腾宁科技做网站399元全包题目 131. 分割回文串
给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
答案#xff1a;
class Solution {boolean[][] f;ListListString请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
答案
class Solution {boolean[][] f;ListListString ret new ArrayListListString();ListString ans new ArrayListString();int n;public ListListString partition(String s) {n s.length();f new boolean[n][n];for (int i 0; i n; i) {Arrays.fill(f[i], true);}for (int i n - 1; i 0; --i) {for (int j i 1; j n; j) {f[i][j] (s.charAt(i) s.charAt(j)) f[i 1][j - 1];}}dfs(s, 0);return ret;}public void dfs(String s, int i) {if (i n) {ret.add(new ArrayListString(ans));return;}for (int j i; j n; j) {if (f[i][j]) {ans.add(s.substring(i, j 1)); dfs(s, j 1); // #A 为什么这里入参是j1而不是i1ans.remove(ans.size() - 1);}}}
}作者力扣官方题解
链接https://leetcode.cn/problems/palindrome-partitioning/solutions/639633/fen-ge-hui-wen-chuan-by-leetcode-solutio-6jkv/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。疑问dfs(s, j 1); 入口 为什么这里入参是j1而不是i1
首先看一下dfs(s, j 1);入口参数是j1的回溯过程
以aab为例我们dfs的流程是
添加a---
继续添加a---
继续添加b---
继续dfs发现ilen越界将答案[a,a,b]加入到ret里然后返回--
在res中删除最后添加的b并且发现当前层dfs的for循环不能再执行了于是自然返回---
res继续删除末尾的a,再次for循环更长的回文串但发现ab不是回文串而且for循环执行不下去了遂返回---
res继续删除末尾的a(空了)然后for循环(i,j)从(0,0)变为(0,1)将对应回文串aa添加---
继续添加b--继续dfs发现ilen越界将答案[aa, b]加入到ret然后返回---
在res中删除最后添加的b发现for不能执行了自然返回---
res继续删除aa再次for循环找更长的回文串(i,j)从(0,1)变成了(0,2)但子串aab不是回文串----
继续for循环发现jlen越界for循环结束最外层调用的dfs函数自然返回。主函数返回结果集ret...打印路径如下
(共7个节点)
i:0,j:0,s.substring(i,j1):a
i:1,j:1,s.substring(i,j1):a
i:2,j:2,s.substring(i,j1):b
i:1,j:2,s.substring(i,j1):ab
i:0,j:1,s.substring(i,j1):aa
i:2,j:2,s.substring(i,j1):b
i:0,j:2,s.substring(i,j1):aab再看一下下面这个棵回溯树
root
|_ a (0,0)|_ a (1,1)|_ b (2,2)|_ ab (1,2)
|_ aa (0,1)|_ b (2,2)
|_ aab (0,2)
把它画成图
使用j1的树中为什么没有|_ ‘aab’ (0,2)的子树
在使用 j1 的方法中代码逻辑会优先尝试将字符串划分为更小的部分也就是说它会先尝试将 aab 分割为 a 和 ab再分割为 a、a 和 b。因此在这个过程中它实际上并没有尝试到 aab 这一整个字符串也就没有 ‘aab’ (0,2) 这个节点。这是因为一旦发现一个回文串它就会立即向后查找而不会尝试更大的字符串。根本原因是 if (f[i][j])的判断
dfs(s, j 1);入口参数是i1的回溯历程
同样的字符串“aab”其打印路径如下
(共经过9个节点)
i:0,j:0,s.substring(i,j1):a
i:1,j:1,s.substring(i,j1):a
i:2,j:2,s.substring(i,j1):b
i:1,j:2,s.substring(i,j1):ab
i:0,j:1,s.substring(i,j1):aa
i:1,j:1,s.substring(i,j1):a
i:2,j:2,s.substring(i,j1):b
i:1,j:2,s.substring(i,j1):ab
i:0,j:2,s.substring(i,j1):aab对应的树如下
使用i1的树中为什么没有|_ ‘aab’ (0,2)的子树
对于 aab‘aab’ (0,2) 是整个字符串是无法继续划分的所以没有子树。之所以在使用 i1 的树中有 aab 这一节点是因为每次 dfs 的入参增加了1所以即使前一步已经找到了一个完整的回文串如 aa也会尝试下一步从而导致 aab 被添加到树中。但是因为 aab 不是回文串所以不会有对应的有效划分即没有子树。
区别
可以看出改变 dfs(s, j 1) 为 dfs(s, i 1)后树中多出了一些节点这是为什么呢使用j1作为入参后似乎更像是做切割表明之前的部分与此无关后者更像是还会重复做一些判断
使用 dfs(s, j 1) 和 dfs(s, i 1) 的差别主要体现在搜索的方向和重复判断上。 dfs(s, j 1): 这是一种前向搜索的策略每次找到一个回文串都会立即查找该回文串后面的所有可能划分。这意味着当你进行下一次递归调用时你已经完成了当前位置之前的所有搜索你将不需要再次考虑这些部分。也就是说这种策略有效地避免了重复判断。 dfs(s, i 1): 这是一种深度搜索策略每次只前进一个位置然后尝试所有可能的划分。这意味着在每个位置你都需要考虑所有的可能划分即使这些划分在之前已经被考虑过。因此这种策略会产生一些重复的判断和多余的节点。
这就是为什么改变 dfs(s, j 1) 为 dfs(s, i 1) 后树中会多出一些节点。而使用 j 1 的策略可以减少这种重复使得搜索更高效。
什么是前向搜索
前向搜索forward search是一种搜索策略在这种策略下我们从一个起始状态开始然后逐步探索所有可达的状态。这种策略常常在图论、树、动态规划等问题中使用。在你的代码中前向搜索就体现在 dfs(s, j 1) 这一行即每次找到一个回文串后立即查找该回文串之后的所有可能划分。
前向搜索是一种剪枝策略嘛
前向搜索本身并不是一种剪枝策略而是一种搜索策略。它决定了搜索的方向和步骤即从当前状态出发探索所有可以直接到达的状态。然而在某些情况下前向搜索可以减少搜索的空间提高搜索的效率这可以看作是一种隐式的剪枝。比如在这个问题中dfs(s, j1) 就相当于一种前向搜索策略它避免了不必要的重复搜索减小了搜索空间
前向搜索相关力扣题目
在力扣LeetCode上许多题目都可以使用前向搜索策略例如
题目22. 括号生成
题目39. 组合总和
class Solution {ListListIntegerres;ListIntegertmp;public ListListInteger subsets(int[] nums) {int nnums.length;resnew ArrayList();tmpnew ArrayList();dfs(nums,0);return res;}void dfs(int[] nums,int i){res.add(new ArrayList(tmp));for(int ji;jnums.length;j){tmp.add(nums[j]);dfs(nums,j1);tmp.remove(tmp.size()-1);}}
}题目46. 全排列 题目79. 单词搜索 这些题目都可以通过前向搜索的方式从一个状态开始逐步探索所有可能的状态。
如果使用i1搜索应该是全量搜索对吧列出一些相关力扣题目
是的使用 i1 的方法相当于全量搜索。它会尝试所有的可能划分包括一些在实际中并不需要的划分。在力扣LeetCode上很多需要遍历所有可能解的题目都可以使用这种方法例如
题目78. 子集 题目90. 子集 II 题目216. 组合总和 III 题目377. 组合总和 Ⅳ
