题目:
给定一个字符串 s ,请将 s 分割成一些子串,使每个子串都是 回文串 ,返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
输入:s = “google”
输出:[[“g”,“o”,“o”,“g”,“l”,“e”],[“g”,“oo”,“g”,“l”,“e”],[“goog”,“l”,“e”]]
输入:s = “aab”
输出:[[“a”,“a”,“b”],[“aa”,“b”]]
输入:s = “a”
输出:[[“a”]]
提示:
1 <= s.length <= 16
s 仅由小写英文字母组成
分析:
输入字符串“google”,假设处理到第一个字符‘g’,此时包括字符‘g’在内后面一共有6个字符,所以此时面临6个选项,也就是分割出6个以字符‘g’开头的子字符串,分别是g,go,goo,goog,googl,google。其中只有g和goog是回文子字符串,再用同样的方法分割后面的字符串。
解决这个问题同样需要很多步,每一步分割出一个回文子字符串,如果处理到某个字符时包括该字符在内后面有n个字符,就面临n个选项。
具体细节见代码
代码:
import java.util.LinkedList;
import java.util.List;
public class Partition {
public static void main(String[] args) {
Partition partition = new Partition();
String s = "google";
List<List<String>> partition1 = partition.partition(s);
System.out.println(partition1);
}
public List<List<String>> partition(String s) {
LinkedList<List<String>> result = new LinkedList<>();
//第一个参数是字符串,第二个参数是起始位置
helper(s,0,new LinkedList<>(),result);
return result;
}
private void helper(String str, int start, LinkedList<String> substrings, LinkedList<List<String>> result) {
if (start == str.length()){
result.add(new LinkedList<>(substrings));
return;
}
//i从下标start开始,到字符串s的最后一个字符结束的每个子字符串是否为回,如果是回文就分割出一个符合条件的子字符串,添加到substrings
//中,接着处理下标从i+1开始的剩余的字符串,当start等于字符串s的长度时,整个字符串s已经被分割成若干回文字符串。
for (int i = start; i < str.length(); i++) {
if (isPalindrome(str,start,i)){
//已经判断是回文字符串了
substrings.add(str.substring(start,i+1));
helper(str,i+1,substrings,result);
substrings.removeLast();
}
}
}
//判断是否是回文字符串
private boolean isPalindrome(String str, int start, int end) {
//首尾指针分别指向字符串的首部尾部,然后相向同时遍历,比较两个指针指向的字符是否相同,如果相同则接着遍历,不同则直接返回false,直到遍历完
//字符串,最终返回true,证明是回文字符串
while (start<end){
if (str.charAt(start++) !=str.charAt(end--)){
return false;
}
}
return true;
}
}