Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]
1 图示:双重循环的逻辑
ajhdfhjfbhjrfbkef
s i i+1 i+2...
s i i+1 i+2...
2 递归的思想:start变成i+1, i相应往后。start的变化是在递归里完成的。
for(int i=start;i<s.length();i++){ 从变量循环 if(isPal(s,start,i)){ list.add(s.substring(start,i+1)); dfs(s,i+1,list,res); start变成i+1, i相应往后。start的变化是在递归里完成的。 list.remove(list.size()-1); } }
3 不知道isPalindrome(String s, int low, int high)要这样写,更方便
4 length()要加括号
class Solution { public List<List<String>> partition(String s) { //cc List<String> temp = new ArrayList<>(); List<List<String>> result = new ArrayList<>(); if (s == null) return null; if (s.length() == 0) return result; dfs(s, 0, temp, result); return result; } public void dfs(String s, int start, List<String> temp, List<List<String>> result) { if (start == s.length()) { result.add(new ArrayList(temp)); }else { for (int i = start; i < s.length(); i++) { if (isPalindrome(s, start, i)) { temp.add(s.substring(start, i + 1)); dfs(s, i + 1, temp, result); temp.remove(temp.size() - 1); } } } } //isPalindrome public boolean isPalindrome(String s, int start, int end) { while (start < end) { if (s.charAt(start++) != s.charAt(end--)) return false; } return true; } }