Leetcode之回溯法专题-131. 分割回文串(Palindrome Partitioning)

Leetcode之回溯法专题-131. 分割回文串(Palindrome Partitioning)网址:yii666.com<文章来源地址:https://www.yii666.com/article/756263.html


给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。文章来源地址https://www.yii666.com/article/756263.html网址:yii666.com

返回 s 所有可能的分割方案。

示例:文章地址https://www.yii666.com/article/756263.html

输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]

分析:给定一个字符串,要求分割,并且要求分割出来的所有的串是回文串。
利用回溯,每次dfs分两个分支 1、不分割继续往下 2、分割后在往下 代码中dfs函数str存放字符串,n存放总长度,step存放当前位置,now是现在已经分割出来的字符串,
remain是字符串剩余还没有分割的,list里装的是分割出来的now 另外加了一个函数来判断,是否为回文串。
class Solution {
List<List<String>> ans = new ArrayList<>(); public List<List<String>> partition(String s) {
if (s.length() == 0 || s == null) {
return ans;
}
dfs(s,s.length(),0,"",s,new ArrayList<String>());
return ans;
} public void dfs(String str, int n, int step, String now, String remain,
ArrayList<String> list) { if (n == step) { if (!now.equals("") && isPalindrome(now)) {
list.add(now);
ans.add(new ArrayList<>(list));
list.remove(list.size() - 1);
}else if(!remain.equals("") && isPalindrome(remain)){
list.add(remain);
ans.add(new ArrayList<>(list));
list.remove(list.size() - 1);
}else if(list.size()!=0 && String.join("",list).equals(str)){ ans.add(new ArrayList<>(list));
} return;
} dfs(str, n, step + 1, now + str.charAt(step),
remain.replaceFirst(str.charAt(step) + "", ""), list); if (!now.equals("") && isPalindrome(now)) {
// System.out.println(step+" "+now + " " + remain);
list.add(now);
dfs(str, n, step + 1, remain.charAt(0)+"", remain.replaceFirst(remain.charAt(0)+"", ""), list);
list.remove(list.size() - 1); } } public boolean isPalindrome(String str) { for (int i = str.length()-1, j = 0; i>=0 && j<=str.length() && i!=j; i--, j++) {
if (str.charAt(i) != str.charAt(j)) {
return false;
}
}
return true;
}
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

Leetcode之回溯法专题-131. 分割回文串(Palindrome Partitioning)-相关文章

  1. PCL—点云分割(最小割算法) 低层次点云处理

  2. PCL—点云分割(基于凹凸性) 低层次点云处理

  3. PCL—点云分割(超体聚类) 低层次点云处理

  4. [CC]手动点云分割

  5. Leetcode之回溯法专题-131. 分割回文串(Palindrome Partitioning)

  6. 3D点云点云分割、目标检测、分类

    3D点云点云分割、目标检测、分类原标题Deep Learning for 3D Point Clouds: A Survey作者Yulan Guo, Hanyun Wang, Qingyong Hu, Hao Liu, Li Liu, and Mohammed Bennamoun原文参考链接:https://arxiv.org/abs/1912.12033导读3D点云学*( Point Clouds)作为*年来的研究热点之一,受到了广泛关注,每年在各大会议上都有大量

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png