刷题记录 - 回文系列 - 《学习笔记》

564. 寻找最近的回文数

给定一个整数 n ，你需要找到与它最近的回文数（不包括自身）。
“最近的”定义为两个整数差的绝对值最小。
示例 1:
输入: “123”
输出: “121”

注意:

n 是由字符串表示的正整数，其长度不超过18。
如果有多个结果，返回最小的那个。

思路：
回文性质，只需考虑数字的前一半即可，奇偶属于不同情况
特别注意：
99 -> 101
1001 -> 999
这两类特殊情况
其余均考虑 x - 1, x, x + 1这三种情况即可，其中x是指字符串前一半转成整型表示的数字

class Solution {
    public String nearestPalindromic(String s) {
        Set<Long> set = new HashSet<>();
        Long v = Long.parseLong(s);
        int n = s.length(), m = (n + 1) / 2;
        //两种特殊情况处理
        set.add(power(10, n - 1) - 1);
        set.add(power(10, n) + 1);
        //三类普通情况
        Long pre = Long.parseLong(s.substring(0, m));
        for (Long x = pre - 1; x <= pre + 1; x += 1) {
            StringBuilder sb = new StringBuilder(x.toString());
            if ((n & 1) == 1) {
                String sb2 = new StringBuilder(sb).reverse().substring(1);
                sb.append(sb2);
                set.add(Long.parseLong(sb.toString()));
            } else {
                StringBuilder sb2 = new StringBuilder(sb).reverse();
                sb.append(sb2);
                set.add(Long.parseLong(sb.toString()));
            }
        }
        set.remove(v);
        // System.out.println(set.toString());
        long min = (long)(2e18);
        long res = 0L;
        for (long x : set) {
            Long minus = Math.abs(v - x);
            if (minus < min) {
                min = minus;
                res = x;
            }else if (minus == min) {
                res = Math.min(res, x);
            }
        }
        return String.valueOf(res);
    }
    long power(long x, int n) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) == 1)
                res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
}

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = “babad” 输出：“bab” 解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd” 输出：“bb”
示例 3：
输入：s = “a” 输出：“a”
示例 4：
输入：s = “ac” 输出：“a”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成

思路：
方法1：区间DP
方法2：中心扩展
方法3：Manacher 算法

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：
输入：s = “abc” 输出：3 解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：s = “aaa” 输出：6 解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

1 <= s.length <= 1000
s 由小写英文字母组成

思路：同5，三种都行！
方法1：区间DP
方法2：中心扩展
方法3：Manacher 算法

//方法1：
class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] f = new boolean[n][n];
        int res = 0;
        for (int i = n - 1; i >= 0; i--)
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || f[i + 1][j - 1])) {
                    f[i][j] = true;
                    res++;
                }
            }
        return res;
    }
}

//方法2：
class Solution {
    int res = 0;
    public int countSubstrings(String s) {
        for (int i = 0; i < s.length(); i++) {
            check(s, i);
        }
        return res;
    }
    void check(String s, int i) {
        int cur = i, j = i;
        while (j >= 0 && i < s.length() && s.charAt(i) == s.charAt(j)) {
            res++;
            i++;
            j--;
        }
        j = cur - 1; i = cur;
        while (j >= 0 && i < s.length() && s.charAt(i) == s.charAt(j)) {
            res++;
            i++;
            j--;
        }
    }
}

1930. 长度为 3 的不同回文子序列

给你一个字符串 s ，返回 s 中 长度为 3 的不同回文子序列 的个数。
即便存在多种方法来构建相同的子序列，但相同的子序列只计数一次。
回文是正着读和反着读一样的字符串。
子序列 是由原字符串删除其中部分字符（也可以不删除）且不改变剩余字符之间相对顺序形成的一个新字符串。

例如，”ace” 是 “abcde“ 的一个子序列。

示例 1：
输入：s = “aabca” 输出：3 解释：长度为 3 的 3 个回文子序列分别是： - “aba” (“aabca“ 的子序列) - “aaa” (“aabca“ 的子序列) - “aca” (“aabca“ 的子序列)
示例 2：
输入：s = “adc” 输出：0 解释：“adc” 不存在长度为 3 的回文子序列。
示例 3：
输入：s = “bbcbaba” 输出：4 解释：长度为 3 的 4 个回文子序列分别是： - “bbb” (“bbcbaba” 的子序列) - “bcb” (“bbcbaba” 的子序列) - “bab” (“bbcbaba” 的子序列) - “aba” (“bbcbaba“ 的子序列)

提示：

3 <= s.length <= 105
s 仅由小写英文字母组成

思路：
方法1：枚举两侧字符，统计中间不同字符的数量。时间复杂度：O(N*|Sigma|)
方法2：枚举中间字符，结合前后缀统计每个字符为中间字符的回文串个数。时间复杂度：O(N + |Sigmal|2)

// 方法1：
class Solution {
    public int countPalindromicSubsequence(String s) {
        int n = s.length(), res = 0;
        for (char ch = 'a'; ch <= 'z'; ch++) {
            int i = 0, j = n - 1;
            while (i < n && s.charAt(i) != ch)
                i++;
            while (j > i && s.charAt(j) != ch)
                j--;
            if (j < i || j == i) continue;
            int cnt = 0, st = 0;
            for (int k = i + 1; k < j; k++) {
                int idx=  s.charAt(k) - 'a';
                if ((st >> idx & 1) == 0) {
                    st |= 1 << idx;
                    cnt++;
                }
            }
            res += cnt;
        }
        return res;
    }
}

//方法2：
class Solution {
    public int countPalindromicSubsequence(String s) {
        int n = s.length();
        int[] pre = new int[n], suf = new int[n];
        for (int i = 0; i < n; i++) {
            int idx = s.charAt(i) - 'a';
            pre[i] = i > 0 ? (pre[i - 1] | (1 << idx)) : (1 << idx); 
        }
        for (int i = n - 1; i >= 0; i--) {
            int idx = s.charAt(i) - 'a';
            suf[i] = i < n - 1 ? (suf[i + 1] | (1 << idx)) : (1 << idx);
        }
        int[] cnt = new int[26];
        for (int i = 1; i < n - 1; i++) {
            int idx = s.charAt(i) - 'a';
            cnt[idx] |= pre[i - 1] & suf[i + 1];
        }
        int res = 0;
        for (int x : cnt)
            res += Integer.bitCount(x);
        return res;
    }
}

336. 回文对

给定一组 互不相同 的单词，找出所有不同的索引对 (i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。

示例 1：
输入：words = [“abcd”,”dcba”,”lls”,”s”,”sssll”] 输出：[[0,1],[1,0],[3,2],[2,4]] 解释：可拼接成的回文串为 [“dcbaabcd”,”abcddcba”,”slls”,”llssssll”]

示例 2：
输入：words = [“bat”,”tab”,”cat”] 输出：[[0,1],[1,0]] 解释：可拼接成的回文串为 [“battab”,”tabbat”]
示例 3：
输入：words = [“a”,””] 输出：[[0,1],[1,0]]
提示：

1 <= words.length <= 5000
0 <= words[i].length <= 300
words[i] 由小写英文字母组成

思路：
方法1：哈希表/字典树 + 枚举
方法2：字典树/哈希表 + Manacher

132. 分割回文串 II

难度困难565
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。

示例 1：
输入：s = “aab” 输出：1 解释：只需一次分割就可将 s 分割成 [“aa”,”b”] 这样两个回文子串。
示例 2：
输入：s = “a” 输出：0
示例 3：
输入：s = “ab” 输出：1

提示：

1 <= s.length <= 2000
s 仅由小写英文字母组成

思路：
预处理+ DP

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] g = new boolean[n][n];
        for (int len = 1; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                if (len <= 2)
                    g[l][r] = s.charAt(l) == s.charAt(r);
                else
                    g[l][r] = s.charAt(l) == s.charAt(r) && g[l + 1][r - 1];
            }
        }
        int[] f = new int[n];
        Arrays.fill(f, 0x3f3f3f3f);
        for (int i = 0; i < n; i++) {
            if (g[0][i])
                f[i] = 0;
            else {
                for (int j = 1; j <= i; j++) {
                    if (g[j][i])
                        f[i] = Math.min(f[i], f[j - 1] + 1);
                }
            }
        }
        return f[n - 1];
    }
}

1278. 分割回文串 III

给你一个由小写字母组成的字符串 s，和一个整数 k。
请你按下面的要求分割字符串：

首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。

请返回以这种方式分割字符串所需修改的最少字符数。

示例 1：
输入：s = “abc”, k = 2 输出：1 解释：你可以把字符串分割成 “ab” 和 “c”，并修改 “ab” 中的 1 个字符，将它变成回文串。
示例 2：
输入：s = “aabbc”, k = 3 输出：0 解释：你可以把字符串分割成 “aa”、”bb” 和 “c”，它们都是回文串。
示例 3：
输入：s = “leetcode”, k = 8 输出：0

提示：

1 <= k <= s.length <= 100
s 中只含有小写英文字母。

思路：
预处理 + DP
想到如何定义状态就不难
f[i][j]表示从前i个字符分割称j个回文串最多需要修改的字符数

class Solution {
    public int palindromePartition(String s, int k) {
        int n = s.length();
        int[][] f = new int[n][k + 1];
        for (int i = 0; i < n; i++)
            Arrays.fill(f[i], 0x3f3f3f3f);
        int[][] g = new int[n][n];
        for (int len = 1; len <= n; len ++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                int i = l, j = r;
                int cnt = 0;
                while (i < j) {
                    if (s.charAt(i) != s.charAt(j))
                        cnt++;
                    i++;
                    j--;
                }
                g[l][r] = cnt;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= Math.min(k, i + 1); j++) {
                if (j == 1)
                    f[i][j] = g[0][i];
                else {
                    for (int u = 1; u <= i; u++) {
                        int min =
                        f[i][j] = Math.min(f[i][j], f[u - 1][j - 1] + g[u][i]);
                    }
                }
            }
        }
        return f[n - 1][k];
    }
}