1. question: 分割回文串(中等)
给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/palindrome-partitioning
示例 1:
1 2
| 输入:s = "aab" 输出:[["a","a","b"],["aa","b"]]
|
示例 2:
提示:
1 2
| 1 <= s.length <= 16 s 仅由小写英文字母组成
|
2. answers
这道题,表面上看是从大到小分割。但是本质上可以看成由小到大组合。可以看成组合问题,采用回溯法:
- 第一个元素选择第一个字符,有s.length长度个选择
- 第二个元素从第一个元素的后面开始选择
- …以此类推
- 注意,形成元素后,要判断是否是回文串,如果是,则继续下一个元素;如果不是,那继续寻找本元素;当遍历完整个数组也找不到时,则说明本元素的选择结束。
- 判断回文串,可以采用首尾双指针法。
那么什么时候终止呢?当选择下一个元素的时候,如果起始下标超过了s.length,那么就说明切割完了。此时结束递归并返回。注意回溯。代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| public class Solution_0083 {
public List<List<String>> res = new ArrayList<>(); public LinkedList<String> group = new LinkedList<>();
public boolean isPalindrome(char[] chars, int start, int end) {
while(start <= end) { if(chars[start++] != chars[end--]) return false; }
return true; }
public void recurPartition(char[] chars, int startIndex, int endIndex) {
if(endIndex == chars.length) { res.add(new ArrayList<>(group)); return; }
for (int i = endIndex; i < chars.length; i++) {
if(!isPalindrome(chars, startIndex, i)) continue;
String s = String.valueOf(chars, startIndex, i - startIndex + 1); group.add(s);
recurPartition(chars, i + 1, i + 1);
group.removeLast(); }
}
public List<List<String>> partition(String s) {
char[] chars = s.toCharArray();
recurPartition(chars, 0, 0); return res; }
public static void main(String[] args) { System.out.println();
String str = "a";
Solution_0083 s = new Solution_0083();
List<List<String>> res = s.partition(str);
for(List<String> list: res){
for(String ss: list) System.out.print(ss + "\t");
System.out.println(); } } }
|
为了方便,设置了两个下标,其实每次选择元素的时候,startIndex和endIndex初始值是一样的,因此可以去掉endIndex。
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。