知识点

字符串

思路

暴力,对于每个点s[i],依次向左右延伸,寻找以该点为中心的奇数长度回文字符串(长度至少为1),以及以该点与其右边点为中心的偶数长度回文字符串(长度至少为0)。每次向左右延伸,字符串长度增加2。每次在到达边界或者不构成回文时,使用现在字符串的长度与已储存的最长长度作比较,若当前的更大,则更新,并且更新这个字符串的左端点坐标,最后根据左端点坐标与字符串长度求出答案并返回即可。

代码c++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串
     */

    string longestPalindrome(string s) {
        int len = 0;
        int ans = 0;
       
        for (int i = 0; i < s.size(); i++) {
          //  cout << s[i] << endl;
            for (int l = i - 1, r = i + 1, t = 0; l >= 0 &&
                    r <= s.size() - 1; l--, r++, t++) {
             //   cout << l << "  " << r << endl;
              //  cout << s[l] << "   " << s[r] << endl;
                if (s[l] != s[r]) {
                    if (len < (2 * t) + 1) {
                        ans = l + 1;
                        len = 2 * t + 1;
                        
                    }
                    break;
                }
                if (l == 0 || r == s.size() - 1) {
                    if (len < (2 * t) + 3) {
                        ans = l;
                        len = 2 * t + 3;
                       
                    }
                    break;
                }
            }
           // cout << 1 << "   " << ans << "  " << len << endl;
            for (int l = i, r = i + 1, t = 0; l >= 0 && r <= s.size() - 1; l--, r++, t++) {
                if (s[l] != s[r]) {
                    if (len < 2 * t) {
                        ans = l + 1;
                        len = 2 * t;
                       
                    }
                    break;
                }
                if (l == 0 || r == s.size() - 1) {
                    if (len < (2 * t) + 2) {
                        ans = l;
                        len = 2 * t + 2;
                       
                    }
                    break;
                }
            }
         //   cout << 2 << "   " << ans << "  " << len << endl;
        }
        string anss;
        
            for (int i = ans; i <= ans + len - 1; i++) {
                anss += s[i];
            }

        return anss;
    }
};