字符串：回文

睡不醒的鲤鱼 2021-10-03 每日一题 LeetCode

# 0005. 最长回文子串 (opens new window)

题目

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

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

1
2
3

示例 2：

输入：s = "cbbd"
输出："bb"

1
2

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

解析

中心扩展法，枚举回文子串的中心位置，每次循环需要分奇数和偶数两种情况。

代码

# 0009. 回文数 (opens new window)

题目

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

1
2

示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

1
2
3

示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

1
2
3

提示：

-2^31 <= x <= 2^31 - 1

进阶：你能不将整数转为字符串来解决这个问题吗？

解析

本题可以借鉴 0007. 整数反转的做法，将数字反转后判断是否与原数字相等。

代码

# 0125. 验证回文串 (opens new window)

题目

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

解析

使用头尾双指针不断向中间移动直到相遇，同时移动过程中对比两指针指向的字符是否相同。

代码

class Solution {
public:
    bool isPalindrome(string s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            while (l < r && !isalnum(s[l])) l++;
            while (l < r && !isalnum(s[r])) r--;
            if (tolower(s[l++]) != tolower(s[r--])) return false;
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12

# 0131. 分割回文串 (opens new window)

题目

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

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

解析

DFS 枚举每个子串的分割位置，而分割的依据就是保证当前子串是一个回文串，所以这就需要频繁的对任意截取的一个子串进行检查。

为了提高运行效率，可以在 DFS 之前预处理一个状态数组 f[i][j]，用来表示字符串 s[i] 到 s[j] 这部分子串是不是一个回文串。

代码

class Solution {
    int n;
    vector<vector<bool>> f;
    vector<vector<string>> ans;
    vector<string> path;
public:
    vector<vector<string>> partition(string s) {
        n = s.length();

        f = vector<vector<bool>>(n, vector<bool>(n));
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                if (i == j) f[i][j] = true;
                else f[i][j] = (s[i] == s[j]) && (i + 1 > j - 1 || f[i + 1][j - 1]);
            }
        }

        dfs(s, 0);
        return ans;
    }

    void dfs(string& s, int idx) {
        if (idx == n) {
            ans.push_back(path);
            return;
        }
        for (int i = idx; i < n; i++) {
            if (!f[idx][i]) continue;
            path.push_back(s.substr(idx, i - idx + 1));
            dfs(s, i + 1);
            path.pop_back();
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 0132. 分割回文串 II (opens new window)

题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的最少分割次数。

解析

定义 f[i] 为 s[0] 到 s[i] 这部分子串的最少分割次数，枚举最后一个子串的长度，进行状态递推。

同时在枚举过程中需要重复判断某个子串是否是回文串，所以还需要定义 g[i][j] 表示 s[i] 到 s[j] 这部分子串是不是一个回文串。

代码

class Solution {
public:
    int minCut(string s) {
        int n = s.length();

        vector<vector<bool>> g(n, vector<bool>(n));
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                if (i == j) g[i][j] = true;
                else g[i][j] = (s[i] == s[j]) && (i + 1 > j - 1 || g[i + 1][j - 1]);
            }
        }

        vector<int> f(n, INT_MAX);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (!g[j][i]) continue;
                if (j == 0) f[i] = 0;
                else f[i] = min(f[i], f[j - 1] + 1);
            }
        }
        return f[n - 1];
    }
};