leetcode: Palindrome Partitioning

问题描述

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

 

原问题链接：https://leetcode.com/problems/palindrome-partitioning/

 

问题分析

　　这是个关于回文划分的问题 ，问题的要求是得出所有划分的情况。一开始碰到这个问题的时候，有点找不到思路，我们该怎么来考虑这个问题呢？先从一个最基本的情况开始吧。

　　假定有一个字符串"abcde"，对于这个串来说，它里面的每个单独的字符a, b, c都可以认为是一个回文。所以最起码有这么一个每个单独字符组成的划分情况。可是在字符串里面可能会存在一些回文，这些需要判断和划分出来。我们从最基本的情况来考虑，尝试看能否发现一些规律：

　　假设字符串s本身就是空串，这个时候，我们的划分数为０。对于这种情况可以认为是返回一个空的列表。假设用list来表示它的划分情况，则这里表示为一个空的list，即为[]。

　　对于长度为１的串来说，它有一个唯一的划分，就是包含这个元素本身。所以它的划分为[i]，假设i为该元素。

　　再进一步来看长度为２的串。假设这个串为"ab"，这个时候，因为"ab"本身不是回文，所以它的划分只有["a", "b"]这种情况。如果这个串本身为回文呢？比如说这个串为"aa"，这个时候，除了前面单个元素的["a", "a"]，还要划分["aa"]。进一步细化的分析来看，对于长度为２的串，假定p[i]表示从０开始到元素i的所有划分。那么它所有的划分则如下，我们首先看长度为０的情况，当0到i的串构成一个回文，则对应长度０和这个回文串构成一个划分，比如这里的"aa"。在长度为１的情况，对应第一个元素的所有划分情况为["a"]，而后面的这个元素是单独的一个元素，也是一个回文，所以它们构成划分["a", "b"]或者["a", "a"]。这样，我们可以概括出一个这样的规律，

p[i] = p(k) + substring(k, i)，if(substring(k, i)) 是回文。k = 0, 1, ... i

    按照这个递归的关系，我们尝试递推一下划分的数量，比如有如下图的字符串：

     假定p[i]表示对应前面i个元素，则有如下的情况：

p[0] = [] 这个时候没有选择任何元素，所以为空。

p[1] = ["a"]，仅有一个元素，选择"a"。

p[2] = ["a", "b"]，我们首先看0到２，这个时候的两个元素为ab，它们不是回文，所以应该跳过。然后再看1到２，因为是单独的a和b，所以有p[2] = p[1] + "b"。如下图：

 

p[3] = ["aba"] ["a", "b", "a"]，还是老样子从0开始看，从0到3的串为aba，它本身为回文，所以应该加入到里面。后面的1和２到３都不构成回文，所以跳过。

 

p4= ["a", "bab"] ["aba", "b"] ["a", "b", "a", "b"]它分别对应着p[1] + "bab", p[3] + "b"。这里p[3] + "b"对应有两种情况，就是前面的["aba", "b"]和["a", "b", "a"]。

　　所以，前面说了这么多，这个递推的关系就是每次对元素前面的部分进行遍历，如果前面遍历的某个点和当前点构成回文，则将这个回文部分和前面的对应点部分拼起来，这样就构成了一个划分。用伪代码描述的话，则如下：

 

for(int j = 0; j <= i; j++) {
    if([i, j]为回文) {
        for(list l : lists[j]) {
            newl = clone(l) // 做一份原来list的copy
            newl.add(s[j, i]); //将j到i的这部分字符串加入到新串中。
            list[i].add(newl); //这时候newl对应着一个划分，将它加入到i所在的划分集合中。
        }
    }
}

     这部分代码对应的是在长度为i的情况下，我们设定这个位置对应的划分列表。仔细看这部分代码的话，还要一个问题就是我们需要考虑的。因为这里有一个判断就是[i, j]这一段字符串是否为回文。所以，有了前面的基础之后，我们需要仔细考虑一下怎么判断它们。如果我们只是每次拿到一个序列的开头就这么去遍历的判断，这样虽然可行，但是很多时候是重复执行了很多运算的。所以这部分也需要仔细考虑一下。

 

回文判断和改进

　　如果单纯从对一个字符串是否为回文的角度来判断的话，我们可以很简单的通过一个for循环从两头往中间比较来实现。在这个问题的场景中，我们需要比对对应位置i来说，从0开头到i之间所有子串。如果每次都这么循环的比对，似乎效率比较低。那么，能否通过一种方式将结果记录下来方便后面直接查找呢？

　　对于字符串来说，假设它的长度为n，那么对应的可能有n * n种。所以，我们可以考虑用一个n * n的矩阵来记录。对于里面所有i == j的情况，相当于对应这个i元素本身。所以如果用一个矩阵p[][]来表示这些判断的话，那么p[i][i] == true。

　　再延伸一下，如果i,j 之间相差一个呢？这就是说这两个元素是相邻的，要判断它们是否为回文，只要保证s[i] == s[j]就可以了。所以对于相邻的元素p[i-1][i] = p[i-1] == p[i]。

　　如果我们再概括到一个更一般的情况呢？如下图，我们考察字符串s[i, j]:

 

     对于这个串来说，如果开头结尾的s[i]和s[j]不相等的话，它肯定就不是一个回文了。如果它们相等呢？这个时候就取决于里面的s[i+1, j-1]这个子串了。如果里面这个是，s[i, j]就是。所以，通过这一系列的讨论，我们又得到一个如下的递推关系：

    假设j >= i。

1. i == j时，p[i][j] = true

2. j == i + 1时，p[i][j] = s[i] == s[j]，取决于相邻两个元素是否相等。

3. 其他，p[i][j] = (s[i] == s[j]) && p[i+1][j-1]。针对递归的情况，取决于当前两个元素是否相等且内部的子串是否也是回文。

　　经过这一番讨论，我们就得到了一个判断回文的递归表达式。将回文判断结果保存到一个矩阵里的方法实现如下：

 

 

void checkPalindrome(String s) {
    int n = s.length();
       boolean[][] p = new boolean[n][n];
       for(int j = 0; j < n; j++) {
            for(int i = 0; i <= j; i++) {
                if(i == j) p[i][j] = true;
                else if(j - i == 1) p[i][j] = s.charAt(i) == s.charAt(j);
                else p[i][j] = p[i+1][j-1] && (s.charAt(i) == s.charAt(j));
            }
       }
}

 

 

实现和改进

 　　有了前面判断某两个节点之间是否构成回文的基础，我们再把前面划分的部分详细做一个实现：

 

public class Solution {
    boolean[][] pair;
    public List<List<String>> partition(String s) {
        checkPalindrome(s);
        int len = s.length();
        List<List<String>>[] result = new List[len + 1];
        result[0] = new ArrayList<List<String>>();
        result[0].add(new ArrayList<String>());
        for(int i = 0; i < s.length(); i++){
            result[i + 1] = new ArrayList<List<String>>();
            for(int j = 0; j <= i; j++){
                if(pair[j][i]){
                    String str = s.substring(j, i + 1);
                    for(List<String> r : result[j]){
                        List<String> ri = new ArrayList<String>(r);
                        ri.add(str);
                        result[i + 1].add(ri);
                    }
                }
            }
        }
        return result[len];
    }
}

     因为我们前面需要利用checkPalindrome方法生成的boolean[][]矩阵，所以将这个矩阵定义成类的成员变量。这里的实现有几个要注意的细节点。

　　一个就是我们设定的数组result[]长度为len + 1。这是因为我们前面归纳设定的长度为０的元素分割为０，它是一个空的list。这样依次类推的话，第一个元素对应string里面的索引０，但是对应这个保存长度result[]里的长度为１的元素，所以要保存最终s.length()的那个元素对应的分割则需要用到n + 1个。用n个还是n+1个元素来保存结果这是动态规划方法里经常需要考虑的。如果是从０个元素作为归纳的开始的话，通常是用到n+1个元素长度的数组。 

     还要一个需要注意的就是我们要保存它们的划分，所以对应一个位置的元素它可能包含的划分有若干个。而每个划分里的元素就是这些子串。所以每个元素对应的数据结构是List<List<String>>。而因为我们这里要保存整个数组的划分结果，所以保存这些划分的数据结构result为List<List<String>>[]。

　　这样，到这一步我们的分析就差不多结束了从实现代码的角度来说，我们实际上还是可以让它变得更加简练一些的。因为每次我们走到一个元素的时候，它的划分判断只依赖于它本身和前面所有的元素。我们的回文判断可以和划分的构建放到一块。按照这个思路，我们可以得到如下的代码：

 

public class Solution {
    public List<List<String>> partition(String s) {
        int len = s.length();
        List<List<String>>[] result = new List[len + 1];
        result[0] = new ArrayList<List<String>>();
        result[0].add(new ArrayList<String>());
        boolean[][] pair = new boolean[len][len];
        for(int i = 0; i < s.length(); i++) {
            result[i + 1] = new ArrayList<List<String>>();
            for(int j = 0; j <= i; j++) {
                if(s.charAt(i) == s.charAt(j) && (i - j < 2 || pair[j + 1][i - 1])) {
                    pair[j][i] = true;
                    for(List<String> r : result[j]) {
                        List<String> ri = new ArrayList<String>(r);
                        ri.add(s.substring(j, i + 1));
                        result[i + 1].add(ri);
                    }
                }
            }
        }
        return result[len];
    }
}

 

总结

　　这个问题其实可以划分为两个层次。首先一个是对划分关系的一个推导。我们根据这个得到一个递推的关系。然后，根据递推关系里，我们需要判断给定两个位置见的子串是否为回文。这里对回文的判断又是一个递推的关系。这两层的关系都可以通过动态规划的方式来解决。这个问题比较复杂，难就难在要从最初的情况里能够推导出这些关系。