H*****l
发帖数: 1257 | 1 原题是Leetcode上的Palindrome Partitioning
如下：
Given a string s, partition s such that every substring of the partition is
a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
--------------------------------------------------------
请问，dfs函数里，这一小段是什么用处啊？特别是最后的remove..
for(int i=start+1;i<=s.length();i++){
if(isPalin(s,start,i-1)){
al.add(s.substring(start,i));
dfs(s,i,al);
al.remove(al.size()-1);
}
}
全部的代码如下：
public class Solution {
ArrayList> all=new ArrayList>();
boolean isPalin(String s, int i, int j){
while(i
if(s.charAt(i)!=s.charAt(j)) return false;
i++;
j--;
}
return true;
}
void dfs(String s, int start, ArrayList al){
if(start==s.length()){
all.add(new ArrayList(al));
return;
}
for(int i=start+1;i<=s.length();i++){
if(isPalin(s,start,i-1)){
al.add(s.substring(start,i));
dfs(s,i,al);
al.remove(al.size()-1);
}
}
}
public ArrayList> partition(String s) {
all.clear();
ArrayList al=new ArrayList();
dfs(s,0,al);
return all;
}
} |
|
