我的Bilibili频道：香芋派Taro
我的个人博客：taropie0224.github.io（阅读体验更佳）
我的公众号：香芋派的烘焙坊
我的音频技术交流群：1136403177
我的个人微信：JazzyTaroPie

https://leetcode.cn/problems/longest-palindromic-substring/

题解and思路

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
public:
    string longestPalindrome(string s) {
        //定义两个数组，用于存放在该位置时进行中心扩散能得到的最大的符合回文子串的长度
        int arr1[s.length()];
        int arr2[s.length()];

        for (int i = 0; i < s.length(); i++) {
            //先判断该位置元素和其右侧的元素是否相等，如示例2中的"bb"情况
            if ((i + 1) < s.length()) { //防止字符串最后一个字符进入判断，因为它右边没有东西了
                if (s[i] == s[i + 1]) { //如果某位置与其右侧相等
                    int left = i - 1; //该位置的左侧
                    int right = i + 2; //其右侧相等字符的右侧
                    int maxLen = 2; //进入判断后的初始最大长度为2
                    if (left >= 0 && right < s.length()) { //边界限定，防止溢出
                        while (s[left] == s[right]) {
                            maxLen += 2; //最大长度每次判断成功加2
                            left--; //向左扩散
                            right++; //向右扩散
                            if (left < 0 || right == s.length()) { //边界限定，防止溢出
                                break; //跳出循环
                            }
                        }
                    }
                    arr1[i] = maxLen; //在位置i时进行中心扩散能得到的最大的符合回文字串的长度
                } else {
                    arr1[i] = 1;
                } 
            } else {
                arr1[i] = 1;
            }

            //再判断是否是示例1的情况，如"bab"
            //具体思路同上
            if ((i - 1) >= 0 && (i + 1) < s.length()) {
                if (s[i - 1] == s[i + 1]) {
                    int left = i - 1;
                    int right = i + 1;
                    int maxLen = 1;
                    if (left >= 0 && right < s.length()) {
                        while (s[left] == s[right]) {
                            maxLen += 2;
                            left--;
                            right++;
                            if (left < 0 || right == s.length()) {
                                break;
                            }
                        }
                        
                    }
                    arr2[i] = maxLen;
                } else {
                    arr2[i] = 1;
                }
            } else {
                arr2[i] = 1;
            }
            //cout<<i<<endl;
        }

        //获得最大元素的下标
        int maxPosition1 = max_element(arr1, arr1 + s.length()) - arr1;
        int maxPosition2 = max_element(arr2, arr2 + s.length()) - arr2;

        //获取两种情况的最长回文子串
        string res1 = s.substr(maxPosition1 - (arr1[maxPosition1] / 2 - 1), arr1[maxPosition1]);
        string res2 = s.substr(maxPosition2 - ((arr2[maxPosition2] - 1) / 2), arr2[maxPosition2]);
        
        //取其中较长的那个输出
        string res = res1.length() > res2.length() ? res1 : res2;

        return res;
    }
};

补充

不好意思可能有些屎山代码了，总结一下遇到的一些问题和解决方案

  1. 分类的思想，即中间位置为1个单独的字符or中间位置为2个相同的字符

  2. 中间碰到了很多次数组溢出，记得在进入前加边界条件判断，并在恰当的时候退出循环

  3. 中心扩散的思想，之前倒是做了很多双指针逼近，其实有点逆向的感觉哈哈

  4. 获取最大最小元素及其下表的方法，如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //求数字最大最小值和其下标
    //vector vector<int> v;
    int maxValue = *max_element(v.begin(), v.end());
    int minValue = *min_element(v.begin(), v.end());
    int maxPosition = max_element(v.begin(), v.end()) - v.begin();
    int minPosition = min_element(v.begin(), v.end()) - v.begin();
    //普通数组 a[]={1,2,3,4,5,6};
    int maxValue = *max_element(a, a + 6);
    int minValue = *min_element(a, a + 6);
    int maxPosition = max_element(a, a + 6) - a;
    int minPosition = min_element(a, a + 6) - a;