题目来源

131. 分割回文串

思路

方法一

dfs

以截取的字符子串是否符合条件，是否是回文串，来判断是否构成一条分支。

如果是回文串，就将这一子串添加到路径中，并开始下一轮搜索。

如果搜索的下标等于字符串长度，就代表搜索完了，将路径添加到答案中。

可以根据树形结构来理解dfs中的for循环

本题的树形结构是一颗多叉树，树形结构如下：

class Solution {
    public List<List<String>> partition(String s) {
        char[] ch = s.toCharArray();
        int len = ch.length;
        List<List<String>> res = new ArrayList();
        Deque<String> path = new ArrayDeque();
        dfs(ch, 0, len, path, res);
        return res;
    }

    public void dfs(char[] ch, int index, int len, Deque<String> path, List<List<String>> res){
        // 搜索完毕，添加到答案中并返回
        if(index == len){
            res.add(new ArrayList(path));	// new一个ArrayList，相当于复制一个path
            return;
        }
        
        // 从下标开始，截取1个、2个、3个、...直到截取下标到字符串最后一个字母为止。
        for(int i = index;i<len;i++){
            
            // 判断是不是回文串，如果不是，就剪枝
            if(!check(ch, index, i)){
                continue;
            }
            // 直接截取字符串会消耗性能，String.substring(String str, int start, int end)，[start,end-1]。
            // 所以用构造方法代替 new String(char[] ch, int index, int len); 从index开始构造长度为len的字符串
            path.addLast(new String(ch, index, i+1-index));
            dfs(ch, i+1, len, path, res);
            path.removeLast();	// 回溯
        }
    }

    // 判断回文串
    public boolean check(char[] ch, int left, int right){
        while(left < right){
            if(ch[left] != ch[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

}

方法二

动态规划+dfs

在方法一中，我们在check方法里面输出每次检查的left指针和right指针，

public boolean check(char[] ch, int left, int right){
    System.out.printf("%d %d\n",left, right);
    while(left < right){
        if(ch[left] != ch[right]){
            return false;
        }
        left++;
        right--;
    }
    return true;
}
/*
以s="aab"为例：
0 0
1 1
2 2
1 2
0 1
2 2（重复）
0 2
*/

会出现重复检查子串是不是回文串的情况，为了避免重复检查，我们使用动态规划来解决这个问题。

我们可以将所有的子串是否是回文，先提前用二维数组存起来。

定义dp子问题：dp[i][j]：从i到j的子串是否为回文。

dp[i][j]为真的情况：

  1. i==j时，子串只有一个字符，肯定是回文
  2. j-1==i时，子串由两个字符组成，字符必须相同s[i] == s[j]
  3. j-1>i时，子串由两个以上的字符组成，s[i] == s[j]，且dp[i+1][j-1] == true 即除去首尾字符的剩余子串也是回文子串

对于1、2、时base case，如下图地蓝色和粉色格子，不需要递推出来，第3点时状态转移方程。我们需要合适的扫描方向，才不会出现：求当前dp[i][j]时，它所以来的dp[i+1][j-1]还没求出来

class Solution {

    char[] ch;
    boolean[][] dp;
    List<List<String>> res;
    Deque<String> path;

    public List<List<String>> partition(String s) {
        ch = s.toCharArray();
        int len = ch.length;
        
        // 预处理
        // 对所有有可能截取的字符串，判断它们是否构成回文串
        dp = new boolean[len][len];
        for(int right = 0;right<len;right++){
            for(int left = 0;left<=right;left++){	// 这里left<=right的情况，相当于上文所说的第一点
                if(left == right){
                    dp[left][right] = true;
                }else if(right - left == 1 && ch[left] == ch[right]){
                    dp[left][right] = true;
                }else if(right - left > 1 && ch[left] == ch[right] && dp[left+1][right-1]){
                    dp[left][right] = true;
                }else{
                    dp[left][right] = false;
                }
            }
        }
        res = new ArrayList();
        path = new ArrayDeque();
        dfs(0, len);
        return res;
    }

    public void dfs(int index, int len){
        if(index == len){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = index;i<len;i++){
            if(dp[index][i]){
                path.addLast(new String(ch, index, i+1-index));
                dfs(i+1, len);
                path.removeLast();
            }
        }
    }
}

参考来源

  1. liweiwei1419
  2. 笨猪爆破组