力扣做题记录——647.回文子串&5.最长回文子串_实验一：力扣 647 50

由于这两题的解法相似，因此本文将直接介绍通用解法，并直接给出两道题的代码。
方法1 动态规划法
首先本题可以使用动态规划法：

• 状态：dq[i][j]表示字符串在[i, j]区间内的子串是否是一个回文串；
• 状态转移方程：当s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])时，dp[i][j] = true，否则为false。

解释：

1. 当只有一个字符时，比如a自然是一个字符串；
2. 当有两个字符时，如果两个字符相等，比如aa，也是一个回文串；
3. 当有三个及以上字符时，比如ababa这个字符串，只要保证其两端字符相等，并且其内部也是回文串，那么整个字符串也是回文串。

代码

// 647.回文子串
int countSubstrings(string s) {
    vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
    int res = 0;
    for (int j = 0; j < s.size(); j++) {
        for (int i = 0; i <= j; i++) {
            if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                res++;
            }
        }
    }
    return res;
}

// 5.最长回文子串
string longestPalindrome(string s) {
    vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
    int max = 0;
    int left = 0;
    int right = 0;
    for (int j = 0; j < s.size(); j++) {
        for (int i = 0; i <= j; i++) {
            if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
            }
            if (dp[i][j] && j - i + 1 > max){
                max = j - i + 1;
                left = i;
                right = j;
            }
        }
    }
    return s.substr(left, right - left + 1);
}
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
35

方法2 中心扩展法
这是一个比较巧妙的方法，实质的思路和动态规划的思路类似。
比如对一个字符串ababa，选择最中间的a作为中心点，往两边扩散，第一次扩散发现left指向的是b，right指向的也是b，所以是回文串，继续扩散，同理ababa也是回文串。
这个是确定了一个中心点后的寻找的路径，然后我们只要寻找到所有的中心点，问题就解决了。
中心点一共有多少个呢？看起来像是和字符串长度相等，但你会发现，如果是这样，上面的例子永远也搜不到abab，想象一下单个字符的哪个中心点扩展可以得到这个子串？似乎不可能。所以中心点不能只有单个字符构成，还要包括两个字符，比如上面这个子串abab，就可以有中心点ba扩展一次得到，所以最终的中心点由2 * len - 1个，分别是len个单字符和len - 1个双字符。
如果上面看不太懂的话，还可以看看下面几个问题：

• 为什么有 2 * len - 1 个中心点？
  aba 有5个中心点，分别是 a、b、c、ab、ba
  abba 有7个中心点，分别是 a、b、b、a、ab、bb、ba
• 什么是中心点？
  中心点即 left 指针和 right 指针初始化指向的地方，可能是一个也可能是两个
• 为什么不可能是三个或者更多？
  因为 3 个可以由 1 个扩展一次得到，4 个可以由两个扩展一次得到
  代码

// 647.回文子串
int countSubstrings(String s) {
    // 中心扩展法
    int ans = 0;
    for (int center = 0; center < 2 * s.size() - 1; center++) {
        // left和right指针和中心点的关系是？
        // 首先是left，有一个很明显的2倍关系的存在，其次是right，可能和left指向同一个（偶数时），也可能往后移动一个（奇数）
        // 大致的关系出来了，可以选择带两个特殊例子进去看看是否满足。
        int left = center / 2;
        int right = left + center % 2;

        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            ans++;
            left--;
            right++;
        }
    }
    return ans;
}

// 5.最长回文子串
pair<int, int> expandAroundCenter(const string& s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        --left;
        ++right;
    }
    return {left + 1, right - 1};
}

string longestPalindrome(string s) {
    int start = 0, end = 0;
    for (int i = 0; i < s.size(); ++i) {
        auto [left1, right1] = expandAroundCenter(s, i, i);
        auto [left2, right2] = expandAroundCenter(s, i, i + 1);
        if (right1 - left1 > end - start) {
            start = left1;
            end = right1;
        }
        if (right2 - left2 > end - start) {
            start = left2;
            end = right2;
        }
    }
    return s.substr(start, end - start + 1);
}
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
35
36
37
38
39
40
41
42
43
44
45