5. Longest Palindromic Substring

Leetcode link

解题思路

本题要求我们找出一个字符串的最长回文子串

一个简单的思路就是遍历字符串，把每一个字符当成回文的中心，求出对应的回文子串的起始下标与结束下标

最后选取最长的一段回文子串返回

C++

class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0, end = 0;
        for(int i = 0;i < s.size();i++) {
            auto [oddLeft, oddRight] = expandAroundCenter(s, i, i);
            auto [evenLeft, evenRight] = expandAroundCenter(s, i, i + 1);
            if(oddRight - oddLeft > end - start) {
                end = oddRight;
                start = oddLeft;
            }
            if(evenRight - evenLeft > end - start) {
                end = evenRight;
                start = evenLeft;
            }
        }
        return s.substr(start, end - start + 1);
    }

    pair<int, int> expandAroundCenter(string& s, int left, int right) {
        while(left >=0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        return {left + 1, right - 1};
    }
};

Javascript

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let start = 0, end = 0;
    for(let i = 0;i < s.length;i++) {
          // 中心只有一个元素的回文
        let [oddLeft, oddRight] = expandAroundCenter(s, i, i);
          // 中心有两个元素的回文
        let [evenLeft, evenRight] = expandAroundCenter(s, i, i + 1);
          // 保存最长的回文子串起始下标与结束下标
        if(oddRight - oddLeft > end - start) {
            start = oddLeft;
            end = oddRight;
        }
        if(evenRight - evenLeft > end - start) {
            start = evenLeft;
            end = evenRight;
        }
    }
    return s.slice(start, end+1);
};

// 计算由回文中心出发的最长回文子串起始与结束下标
var expandAroundCenter = function(s, left, right) {
    while(left >= 0 && right < s.length && s[left] === s[right]) {
        left--;
        right++;
    }
    return [left + 1, right - 1];
}