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;
}
} | c***d
发帖数: 26 | 2 这是递归／回溯很基本的技巧呀。
leetcode上很多题用这技巧。
建议先看看permutation/combination那几题，你就能明白了。
is
【在 H*****l 的大作中提到】
: 原题是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"]
| r********7
发帖数: 102 | 3 先判断 子句是不是 palindrome
然后切掉子句 继续寻找palindrome的子句。。 进行递归
最后 清除子句 清除al arraylist, 进行下一个循环。
大概就是这样。。
可以设个断点，自己研究下
is
【在 H*****l 的大作中提到】
: 原题是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"]
| r*c
发帖数: 167 | 4 发现小bug一只
al.add(s.substring(start,i));
应该是
al.add(s.substring(start,i-start)); |
|
