Palindrome Partitioning - Leetcode

思路：在每一步，一一往前搜索并验证是否是回文，如果当前不是回文则停止前进，返回上一个状态并记录。每一次都搜索到结尾，因为这里要累计回文子串。回溯法就可以用到，在这里。

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"]]

public class Solution {public List<List<String>> partition(String s) {boolean[][] f = new boolean[s.length()][s.length()];for (int i = f.length - 1; i >= 0; i--) {for (int j = i; j < f.length; j++) {if (s.charAt(i) == s.charAt(j)&& (j - i < 2 || f[i + 1][j - 1] == true))f[i][j] = true;}}HashMap<Integer, List<List<String>>> hm = new HashMap<>();for (int i = f.length - 1; i >= 0; i--) {for (int j = i; j < f.length; j++) {if (f[i][j]) {String parlindrome = s.substring(i, j + 1);if (j < f.length - 1) {for (List<String> kks_list : hm.get(j + 1)) {List<String> ls = new ArrayList<>(kks_list);ls.add(0, parlindrome);if (!hm.containsKey(i)) {List<List<String>> kks = new ArrayList<>();kks.add(ls);hm.put(i, kks);} elsehm.get(i).add(ls);}} else {ArrayList<String> as = new ArrayList<String>();as.add(parlindrome);List<List<String>> lls = new ArrayList<>();lls.add(as);if (!hm.containsKey(i))hm.put(i, lls);elsehm.get(i).add(as);}}}}return hm.get(0);}
}

public class Solution {public List<List<String>> partition(String s) {List<List<String>> result = new ArrayList<>();List<String> path = new ArrayList<>();DFS(s, result, 0, path);return result;}private void DFS(String s, List<List<String>> result, int start, List<String> path){if(start == s.length()){result.add(<span style="background-color: rgb(255, 255, 51);">new ArrayList<String>(path)</span>);return;}for(int i=start; i<s.length(); i++){if(isPalindrome(s,start,i)){ // cut from iString sub = s.substring(start, i+1);path.add(sub);DFS(s, result, i+1, path); //continue cuttingpath.remove(path.size()-1);}}}private boolean isPalindrome(String s, int start, int end){while(s.charAt(start) == s.charAt(end) && start<end){start++;end--;}return start>=end;}
}