给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
这算是backtrack的经典题目了。首先我们需要一个isPalindrome
函数判断是不是回文字符串,思路很简单,就是从字符串的两端检查到中间。接下来就是backtrack的过程。如下图,从左到右是循环的过程,对于你代码中的for循环,每次循环,字符加一个:a -> aa -> aab。而每次递归就是进入子问题进行深度搜索的过程。
递归过程
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new LinkedList<>();
if (s == null || s.length() == 0) { return res;}
List<String> current = new LinkedList<>();
helper(res, current, s, 0);
return res;
}
public void helper(List<List<String>> res, List<String> current, String s, int startIndex) {
if (s.length() == startIndex) {
res.add(new LinkedList<>(current));
return;
}
for (int i = startIndex; i < s.length(); i++) {
String currentPartition = s.substring(startIndex, i + 1);
if (currentPartition.isEmpty() || !isPalindrome(currentPartition)) {
continue;
}
current.add(currentPartition);
helper(res, current, s, i+1);
current.remove(current.size() - 1);
}
}
public boolean isPalindrome(String s) {
char[] res = s.toCharArray();
int left = 0;
int right = s.length() - 1;
while (left <= right) {
if (res[left] !=res[right]) {
return false;
}
left++;
right--;
}
return true;
}
}
本文分享自 Leetcode名企之路 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!