200. Longest Palindromic Substring

class Solution {
public:
    /**
     * @param s: input string
     * @return: the longest palindromic substring
     */
    string longestPalindrome(string &s) {
        // write your code here
        int sizeS = s.size();
        if(sizeS <= 1){
            return s;
        }
        int maxLen = 0;
        string res;
        for(int i = 0; i < sizeS; i++){
            //1，已i元素为中心
            int wing = 1;
            while(i - wing >= 0 && i + wing < sizeS && s[i - wing] == s[i + wing]){
                wing++;
            }
            if((wing - 1) * 2 + 1 > maxLen){
                maxLen = wing * 2 - 1;
                res = s.substr(i - wing + 1, maxLen);
            }
            //2，以i和i+1 已i元素为中心
            if(i + 1 < sizeS && s[i] == s[i + 1]){
                wing = 1;
                 while(i - wing >= 0 && i + 1 + wing < sizeS && s[i - wing] == s[i + 1 + wing]){
                     wing++;
                 }
                 if((wing * 2) > maxLen){
                     maxLen = wing * 2;
                     res = s.substr(i - wing + 1, maxLen); //注意substr语法，第二项是长度
                 }
            }
         
        }
     return res;

    }
};


2019年3月6日10:42:04 二刷
class Solution { public: /** * @param s: input string * @return: the longest palindromic substring */ string longestPalindrome(string &s) { // write your code here //和837. Palindromic Substrings一样的解法，那里是找所有的个数，这里是找最长的 //DP state: dp[i][j], i和j之前的substr是否是pali. //transition: s[i] = s[j]时：true if dp[i + 1][j - 1] || j - i <= 2 //Initial: 不需要？ //result：遍历过程中找最大length //这道题 不用DP，结果暴力解，遍历s中每个元素，然后找以每个元素为中心的pali，比DP更节省空间复杂度 const int n = s.size(); int maxLen = INT_MIN; int maxStart = 0; std::vector<vector<int>> dp(n, vector<int>(n, 0)); for(int i = n - 1; i >= 0; i--){ for(int j = i; j < n; j++){ if(s[i] == s[j]){ dp[i][j] = (j - i <= 2) || (dp[i + 1][j - 1]); } if(dp[i][j] && maxLen < j - i + 1){ maxLen = j - i + 1; maxStart = i; } } } return s.substr(maxStart, maxLen); } };