回溯法（1）算法

原题：

/** * Created by pradhang on 3/15/2017. * 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"] * ] */

【回溯法（1）】答案：

public class PalindromePartitioning { /** * Main method * * @param args * @throws Exception */ public static void main(String[] args) throws Exception { List result = new PalindromePartitioning().partition("aaaaaaaaaaaaaaaaaa"); }public List partition(String s) { List result = new ArrayList<>(); doNext(0, new ArrayList<>(), s, result); return result; }private void doNext(int i, List row, String s, List result) { if (i == s.length()) { List list = new ArrayList<>(row); result.add(list); } else { for (int j = i, l = s.length(); j < l; j++) { String sbStr = s.substring(i, j + 1); if (isPalindrome(sbStr)) { row.add(sbStr); doNext(j + 1, row, s, result); row.remove(row.size() - 1); } } } }private boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while (i <= j) { if (s.charAt(i) != s.charAt(j)) return false; i++; j--; } return true; } }