Palindrome Partitioning(Medium) 回文分割

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

题意分析： 对输入的字符串划分为一组回文字符串。

解题思路：动态规划

assuming the total number of strings is k, then the complexity is O(n^2×k).

isPalindrome[i][j]=1的话，表明：string[i..j]是一个回文字符串。

其中一个知识点是：划分的时候判断isPalindrome[i][j]是否是回文串，需要用到：isPalindrome[i+1][j-1]的值，所以生成标志回文字符串的数组的时候外层循环要从 s.length()-1 开始逐次递减。

public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++)
            isPalindrome[i][i] = true;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    //j-i<2表示只需比较2个字符,其索引分别为i和j
                    if (j - i < 2 || isPalindrome[i + 1][j - 1])
                        isPalindrome[i][j] = true;
                }
            }
        }

        List<List<String>>[] palindromes = (List<List<String>>[]) Array.newInstance(List.class, n + 1);

        palindromes[n] = (List)(new LinkedList<List<String>>());
        List<String> emptyList = new LinkedList<>();
        palindromes[n].add(emptyList);

        for (int i = n - 1; i >= 0; i--) {
            palindromes[i] = (List)(new LinkedList<List<String>>());
            for (int j = i; j < n; j++) {
                if (isPalindrome[i][j]) {
                    List<List<String>> lists = palindromes[j + 1];
                    String substring = s.substring(i, j + 1);
                    for (List<String> list : lists) {
                        List<String> newList = new LinkedList<>();
                        newList.add(substring);
                        newList.addAll(list);
                        palindromes[i].add(newList);
                    }
                }
            }
        }

        return palindromes[0];
 }

解题思路2：DFS+回溯

public class Solution {
    List<List<String>> ret;
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++)
            isPalindrome[i][i] = true;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i < 2 || isPalindrome[i + 1][j - 1])
                        isPalindrome[i][j] = true;
                }
            }
        }
        ret = new LinkedList<>();
        List<String> list = new LinkedList<>();
        partition(s, 0, isPalindrome, list);
        return ret;
    }

    private void partition(String s, int start, boolean[][] isPalindrome, List<String> list) {
        if (start == s.length()) {
            List<String> newList = new LinkedList<>();
            newList.addAll(list);
            ret.add(newList);
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (isPalindrome[start][i]) {
                list.add(s.substring(start, i + 1));
                partition(s, i + 1, isPalindrome, list);
                list.remove(list.size() - 1);
            }
        }
    }
}

References

1 Solution from Life in Code

2 Palindrome Permutation II