最长回文子串「变题」

5. 最长回文子串

开头先来一个小插曲，关于「回文」两种方法的总结可见 回文子串的两种方法：「中心扩展」&「动态规划」

// 中心扩展法
// 时间复杂度 : O(n^2)
// 空间复杂度 : O(n) -> 也可以降低到 O(1) -> 将 String 先转化成 char[] 快一些
public String longestPalindrome(String S) {
    char[] s = S.toCharArray();
    int n = s.length;
    int x = 0, y = 0;
    for (int i = 0; i < 2 * n - 1; i++) {
        int l = i / 2, r = l + i % 2;
        for (; l >= 0 && r < n && s[l] == s[r]; l--, r++) ;
        if (y - x - 1 < r - l - 1) {
            x = l + 1; y = r;
        }
    }
    return S.substring(x, y);
}

// 动态规划法
// 时间复杂度 : O(n^2)
// 空间复杂度 : O(n^2)
public String longestPalindrome(String S) {
    char[] s = S.toCharArray();
    int n = s.length, x = 0, y = 0;
    boolean[][] dp = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (y - x + 1 < j - i + 1) {
                    x = i; y = j;
                }
            }
        }
    }
    return S.substring(x, y + 1);
}

变题一：回文子串

题目详情可见 回文子串

// 中心扩展法
// 时间复杂度 : O(n^2)
// 空间复杂度 : O(n) -> 也可以降低到 O(1) -> 将 String 先转化成 char[] 快一些
public int countSubstrings(String S) {
    char[] s = S.toCharArray();
    int n = s.length, ans = 0;
    for (int i = 0; i < 2 * n - 1; i++) {
        int l = i / 2, r = l + i % 2;
        for (; l >= 0 && r < n && s[l] == s[r]; l--, r++) ;
        ans += (r - l) / 2;
    }
    return ans;
}
// 动态规划法
// 时间复杂度 : O(n^2)
// 空间复杂度 : O(n^2)
public int countSubstrings(String S) {
    char[] s = S.toCharArray();
    int n = s.length, ans = 0;
    boolean[][] dp = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                ans++;
            }
        }
    }
    return ans;
}

变题二：最长回文子序列

题目详情可见 最长回文子序列

关于本题详细总结可见 动态规划之最长回文子序列

public int longestPalindromeSubseq(String S) {
    char[] s = S.toCharArray();
    int n = s.length;
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (s[j] == s[i]) dp[j][i] = dp[j + 1][i - 1] + 2;
            else dp[j][i] = Math.max(dp[j + 1][i], dp[j][i - 1]);
        }
    }
    return dp[0][n - 1];
}
// 空间优化
public int longestPalindromeSubseq(String S) {
    char[] s = S.toCharArray();
    int n = s.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = n - 1; i >= 0; i--) {
        int preDown = 0;
        for (int j = i + 1; j < n; j++) {
            int t = dp[j];
            if (s[i] == s[j]) dp[j] = preDown + 2;
            else dp[j] = Math.max(dp[j], dp[j - 1]);
            preDown = t;
        }
    }
    return dp[n - 1];
}

变题三：让字符串成为回文串的最少插入次数

题目详情可见 让字符串成为回文串的最少插入次数

关于本题详细总结可见 动态规划之最长回文子序列

public int minInsertions(String S) {
    char[] s = S.toCharArray();
    int n = s.length;
    int[][] dp = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
            else dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
        }
    }
    return dp[0][n - 1];
}

变题四：变成回文数的最小代价

题目详情可见 编程题【2021】360编程题回文数变换

所谓回文数就是一个数字，从左边读和从右边读的结果都是一样的，例如12321

现在有一个只包含1、2、3、4的数字，你可以通过在任意位置增加一位数字或者删除一位数字来将其变换成一个回文数。但是增加或删除不同数字所需要的代价是不一样的

已知增加和删除每个数字的代价如下：

• 增加一个1，代价：100；删除一个1，代价：120
• 增加一个2，代价：200；删除一个2，代价：350
• 增加一个3，代价：360；删除一个3，代价：200
• 增加一个4，代价：220；删除一个4，代价：320

请问如何通过最少的代价将一个数字变换为一个回文数。当然，如果一个数字本身已经是一个回文数 (包括一位数，例如：2)，那么变换的代价为0

输入：12322

输出：300

解释：变成 1223221 或者 2123212

public static int minCost(String S) {
    // 对同一个数字增加删除操作取最小值
    int[] cost = new int[]{100, 200, 200, 220};
    char[] s = S.toCharArray();
    int n = s.length;
    int[][] dp = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
            else dp[i][j] = Math.min(dp[i + 1][j] + cost[s[i] - '1'], dp[i][j - 1] + cost[s[j] - '1']);
        }
    }
    return dp[0][n - 1];
}