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，然而实现时犯了一个很大错误。见AC代码。
public class Solution {
public List
> partition(String s) {
List
> res = new ArrayList<>(); List
list = new ArrayList
(); dfs(s, list, res); return res; } public void dfs(String s,List
list,List
> res){ if(s.length()<1){ //巨大错误：！！！ 这里必须注意不能写成res.add(list); 因为后面list会改变，导致最终res里面为空 res.add(new ArrayList
(list)); return; } for(int i=0;i
也可以换种写法思路一样实现有点细微差别：上面是每次改变字符串递归，下面写法是通过下标改变实现字符串变动。
public List
> partition(String s) {
List
item = new ArrayList
(); List
> res = new ArrayList<>(); if(s==null||s.length()==0) return res; dfs(s,0,item,res); return res; } public void dfs(String s, int start, List
item, List
> res){ if (start == s.length()){ res.add(new ArrayList
(item)); return; } for (int i = start; i < s.length(); i++) { String str = s.substring(start, i+1); if (isPalindrome(str)) { item.add(str); dfs(s, i+1, item, res); item.remove(item.size() - 1); } } } public boolean isPalindrome(String s){ int low = 0; int high = s.length()-1; while(low < high){ if(s.charAt(low) != s.charAt(high)) return false; low++; high--; } return true; } }