LeetCode_84_PalindromePartitioning


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
输入:s = "a"
输出:[["a"]]

提示:

1
2
1 <= s.length <= 16
s 仅由小写英文字母组成

2. answers

这道题,表面上看是从大到小分割。但是本质上可以看成由小到大组合。可以看成组合问题,采用回溯法:

  1. 第一个元素选择第一个字符,有s.length长度个选择
  2. 第二个元素从第一个元素的后面开始选择
  3. …以此类推
  4. 注意,形成元素后,要判断是否是回文串,如果是,则继续下一个元素;如果不是,那继续寻找本元素;当遍历完整个数组也找不到时,则说明本元素的选择结束。
  5. 判断回文串,可以采用首尾双指针法。

那么什么时候终止呢?当选择下一个元素的时候,如果起始下标超过了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;
}

// 选择本元素
// 判断是否是回文子串,如果是,则继续递归,直到遍历完整个字符串
// 如果不是,则增大endIndex,直到找到,或者找不到,
// 本元素有多种选择,[startIndex, endIndex]
for (int i = endIndex; i < chars.length; i++) {

// 判断是否是回文串,注意,结束位置,不同的选择是不一样的,因此结束位置是i,而不是固定的endIndex
// 如果不是,则进行当前元素的下一个选择,
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 = "aab";
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)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录