题目链接
思路
使用 DFS
,同时依次检查分割的字符串是否是回文串。
注意:需要频繁添加删除末尾元素时,可以使用 Deque
代码
class Solution {
private List<List<String>> result = new ArrayList<>();
public List<List<String>> partition(String s) {
int len = s.length();
Deque<String> temp = new ArrayDeque<>();
char[] array = s.toCharArray();
dfs(array, 0, len, temp);
return result;
}
private void dfs(char[] array, int index, int len, Deque<String> temp) {
if(index == len){
result.add(new ArrayList<>(temp));
return;
}
for(int i = index; i < len; i++){
if(checkPalindrome(array, index, i)){
temp.add(new String(array, index, i - index + 1));
dfs(array, i + 1, len, temp);
temp.removeLast();
}
}
}
private boolean checkPalindrome(char[] s, int left, int right){
while(left < right){
if(s[left] != s[right]){
return false;
}
left++;
right--;
}
return true;
}
}
标签:index,right,temp,int,DFS,131,len,array,LeetCode
From: https://www.cnblogs.com/shixuanliu/p/17171378.html