Given a strings, partition_s_such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Have you met this question in a real interview?

Yes

Example

Given s ="aab", return:

[
  ["aa","b"],
  ["a","a","b"]
]

1. DFS

the method to address this problem is similar to the subset where we enumerate a position and if it is palindrome then we recursively solve for the remaining of the string.

public class Solution {
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
    public List<List<String>> partition(String s) {
        // write your code here
        List<List<String>> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }

        List<String> cur = new ArrayList<>();

        dfsPartition(ans, cur, s, 0);

        return ans;
    }

    public void dfsPartition(List<List<String>> ans,
                             List<String> cur,
                             String s,
                             int startIndex) {
        //出口
        if (startIndex == s.length()) {
            ans.add(new ArrayList<String>(cur));
            return;
        }


        //拆解 
        for (int i = startIndex + 1; i <= s.length(); i++) {

            String current = s.substring(startIndex, i);
            if (!isPalindrome(current)) {
                continue;
            }
            cur.add(current);
            dfsPartition(ans, cur, s, i);
            cur.remove(cur.size() - 1);
        }
    }


    public boolean isPalindrome(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

faster but longer

public class Solution {
    /*
     * @param s: A string
     * @return: A list of lists of string
     */
    public List<List<String>> partition(String s) {
        // write your code here
        List<List<String>> ans = new ArrayList<>();
        List<String> cur = new ArrayList<>();

        if (s == null || s.length() == 0) {
            ans.add(cur);
            return ans;
        }

        boolean[][] isPalindrome = getIsPalindrome(s);
        //System.out.println(isPalindrome[0][4]);
        dfs(0, s, isPalindrome, cur, ans);
        return ans;
    }

    public void dfs(int startIndex, String s, boolean[][] isPalindrome, List<String> cur, List<List<String>> ans) {
        //exit
        if (startIndex >= s.length()) {
            ans.add(new ArrayList<String>(cur));
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            if (!isPalindrome[startIndex][i]) {
                continue;
            }

            String current = s.substring(startIndex, i + 1);
            cur.add(current);
            dfs(i + 1, s, isPalindrome, cur, ans);
            cur.remove(cur.size() - 1);
        }
    }

    public boolean[][] getIsPalindrome(String s) {
        boolean[][] ans = new boolean[s.length()][s.length()];

        //same value always true
        for (int i = 0; i < s.length(); i++) {
            ans[i][i] = true;
        }

        //neighbour value equals then true, otherwise false

        for (int i = 0; i < s.length() - 1; i++) {
            ans[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }

        //populate the top right of the boolean array, must from the back to the front
        //n - 3 is because n - 1 and n - 2 are known
        for (int i = s.length() - 3; i >= 0; i--) {
            //j = i + 2 is because, i, i + 1 are known
            for (int j = i + 2; j < s.length(); j++) {
                ans[i][j] = ans[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
            }
        }

        return ans;
    }
}