mzoe666888

V1

2022/04/14阅读:21主题:兰青

内卷大厂系列《分割回文串问题二连击》

大厂高频算法面试题:《分割回文串系列》,您将学到怎么写动态规划,一切从尝试入手,先从暴力递归,然后再基于暴力递归改动态规划,本文会介绍两种尝试模型:从左往右的尝试模型和范围尝试模型,而不是硬憋动态规划。

一、回文最少分割数

给定一个字符串 str,返回把 str 全部切成回文子串的最小分割数。

示例

str="ABA"。不需要切割,str 本身就是回文串,所以返回 0。

str="ACDCDCDAD"。最少需要切 2 次变成 3 个回文子串,比如"A"、"CDCDC"和"DAD",所以返回 2。

1、分析

方法一:暴力解,假如字符串str有3个回文串,则需要切2刀,可以先把字符串中是回文串的个数求出来,然后再减去1就是切的刀数。字符串每个位置作为划分切下去,看前缀是不是回文,如果前缀是回文,回文数 = 1 + 后续子过程的解,如果前缀不是回文,则i++,看前缀能不能构成回文,整体时间复杂度为O(N³)

方法二:每次遍历都得验证i...end位置的字符串是不是回文,如果有一张表能直接告诉就好了,所以生成一种dp回文表,就不需要每次遍历验证了,直接从dp表拿值验证。整体时间复杂度为O(N²)

利用范围尝试模型dp[i][j]含义:str[i...j]是不是回文,生成回文dp表的规则如下:

  • 第一条斜对角线好填,i == j,代表一个字符构成的字符串,当然是回文,直接填true
  • 第二条斜对角线也好填,代表2个字符构成的字符串,如果相等则是回文,不等则不是回文
  • 左半部分不用填,无效(i > j)即 L > R
  • 其余格子从第三条斜对角线开始填
  • 整体从下往上,每行从左往右填

从左往右的尝试模型 + 范围尝试模型

2、实现

1、方法一

public static int minParts(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    return process(s.toCharArray(), 0) - 1;
}

// 当前来到i位置,arr[0~i-1]不用管,已经弄好了
// arr[i...N-1] 返回回文数
public static int process(char[] str, int i) {
    if (i == str.length) { // base case
        return 0;
    }
    // i < N
    // i...end 这一段字符串
    int ans = Integer.MAX_VALUE;
    for (int end = i; end < str.length; end++) { // O(N²)
        if (isP(str, i, end)) { // O(N)
            ans = Math.min(ans, 1 + process(str, end + 1));
        }
    }
    return ans;
}

// L...R范围内,校验是否是回文字符串
public static boolean isP(char[] str, int L, int R) {
    while (L <= R) {
        if (str[L] != str[R]) {
            return false;
        }
        L++;
        R--;
    }
    return true;
}

2、方法二

// 从左往右的尝试模型 + 范围尝试模型
public static int minParts(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    return process(s) - 1;
}

public static int process(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    if (s.length() == 1) {
        return 1;
    }
    char[] str = s.toCharArray();
    int N = str.length;
    // 生成回文dp,加速查找
    boolean[][] isP = new boolean[N][N];
    // 第一条和第二条斜对角线
    for (int i = 0; i < N - 1; i++) {
        isP[i][i] = true;
        isP[i][i + 1] = str[i] == str[i + 1];
    }
    isP[N - 1][N - 1] = true;
    // 其余格子,整体从下往上,其次从左往右填
    for (int row = N - 3; row >= 0; row--) {
        for (int col = row + 2; col < N; col++) {
            isP[row][col] = str[row] == str[col] && isP[row + 1][col - 1];
        }
    }
    int[] dp = new int[N + 1];
    for (int i = 0; i <= N; i++) {
        dp[i] = Integer.MAX_VALUE;
    }
    dp[N] = 0;
    for (int i = N - 1; i >= 0; i--) {
        for (int end = i; end < N; end++) {
            // i..end
            if (isP[i][end]) {
                dp[i] = Math.min(dp[i], 1 + dp[end + 1]);
            }
        }
    }
    return dp[0];
}

二、分割回文串

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2

输入:s = "a"
输出:[["a"]]

leetcode

1、分析

str从L...R是不是回文,提前生成一张表,以后再查是不是回文,就不需要遍历了,下边生成的dp其他格子的方式和题目一生成的dp其他格子的方式不一样,都可以。

当前来到index位置开始决定,str[0...index-1] 已经做过的决定,放入了path中,如果 index == str.len,index来到越界位置,path之前做的决定(一种分割方法),放进总答案ans里,其次需要考虑深度优先遍历清理现场:

str = "aabaa"

  • index...index 此时只有一个字符a是前缀回文,放在path中
  • index...index+1 此时path应该是两个字符aa作为前缀回文,上一次的path应该清理掉

2、实现

public static List<List<String>> partition(String s) {
    // dp[L][R] -> 是不是回文
    boolean[][] dp = getdp(s.toCharArray());
    LinkedList<String> path = new LinkedList<>();
    List<List<String>> ans = new ArrayList<>();
    process(s, 0, path, dp, ans);
    return ans;
}

public static boolean[][] getdp(char[] str) {
    int N = str.length;
    boolean[][] dp = new boolean[N][N];
    for (int i = 0; i < N - 1; i++) {
        dp[i][i] = true;
        dp[i][i + 1] = str[i] == str[i + 1];
    }
    dp[N - 1][N - 1] = true;
    for (int j = 2; j < N; j++) {
        int row = 0;
        int col = j;
        while (row < N && col < N) {
            dp[row][col] = str[row] == str[col] && dp[row + 1][col - 1];
            row++;
            col++;
        }
    }
    return dp;
}

// s 字符串
// s[0...index-1] 已经做过的决定,放入了path中
// 在index开始做属于这个位置的决定,
// index == s.len  path之前做的决定(一种分割方法),放进总答案ans里
public static void process(String s, int index, LinkedList<String> path,
                           boolean[][] dp, List<List<String>> ans)
 
{
    if (index == s.length()) {
        ans.add(copy(path));
    } else {
        for (int end = index; end < s.length(); end++) {
            // index..index
            // index..index+1
            // index..index+2
            // index..end
            if (dp[index][end]) { // 前缀是不是回文
                path.addLast(s.substring(index, end + 1));
                process(s, end + 1, path, dp, ans); // 深度优先遍历
                path.pollLast(); // 清除现场
            }
        }
    }
}

public static List<String> copy(List<String> path) {
    List<String> ans = new ArrayList<>();
    for (String p : path) {
        ans.add(p);
    }
    return ans;
}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1