描述
给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。
返回s所有可能的回文串分割方案。
样例
给出 s = "aab"，返回
[
["aa", "b"],
["a", "a", "b"]
]
空集应该算回文
演示
示例
代码
- shorter but slower
public class Solution {
/**
* @param s: A string
* @return: A list of lists of string
*/
public List<List<String>> partition(String s) {
List<List<String>> results = new ArrayList<>();
if (s == null || s.length() == 0) {
// return results表示切割方案为空，对于输入空集也适用
return results;
}
List<String> partition = new ArrayList<String>();
helper(s, 0, partition, results);
return results;
}
private void helper(String s,
int startIndex,
List<String> partition,
List<List<String>> results) {
if (startIndex == s.length()) {
results.add(new ArrayList<String>(partition));
return;
}
for (int i = startIndex; i < s.length(); i++) {
String subString = s.substring(startIndex, i + 1);
// 如果切割的字符串不是回文代表当前 i 位置切割的方案不可行
if (!isPalindrome(subString)) {
continue;
}
partition.add(subString);
helper(s, i + 1, partition, results);
partition.remove(partition.size() - 1);
}
}
// 记住回文判断的写法
private boolean isPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
}
- longer but faster
public class Solution {
List<List<String>> results;
boolean[][] isPalindrome;
/**
* @param s: A string
* @return: A list of lists of string
*/
public List<List<String>> partition(String s) {
results = new ArrayList<>();
if (s == null || s.length() == 0) {
return results;
}
getIsPalindrome(s);
helper(s, 0, new ArrayList<Integer>());
return results;
}
private void getIsPalindrome(String s) {
int n = s.length();
isPalindrome = new boolean[n][n];
for (int i = 0; i < n; i++) {
isPalindrome[i][i] = true;
}
for (int i = 0; i < n - 1; i++) {
isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
}
for (int i = n - 3; i >= 0; i--) {
for (int j = i + 2; j < n; j++) {
isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
}
}
}
private void helper(String s,
int startIndex,
List<Integer> partition) {
if (startIndex == s.length()) {
addResult(s, partition);
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (!isPalindrome[startIndex][i]) {
continue;
}
partition.add(i);
helper(s, i + 1, partition);
partition.remove(partition.size() - 1);
}
}
private void addResult(String s, List<Integer> partition) {
List<String> result = new ArrayList<>();
int startIndex = 0;
for (int i = 0; i < partition.size(); i++) {
result.add(s.substring(startIndex, partition.get(i) + 1));
startIndex = partition.get(i) + 1;
}
results.add(result);
}
}
