Leetcode 5

题目要求

对特定字符串，找出其中的最长回文子串

核心算法和原理

• Solution 1: Double Pointer
• 找回文串要么找中心点，要么找首尾。本题是在很多个子串里找回文串，所以应该使用中心点
• 中心点的算法：设计寻找子串的函数的参数设置为一个原string, 左指针left，右指针right。然后让两个指针向两边发散，逐个匹配，匹配至不符的情况就return这个子串。由于从中心点出发要区分奇偶，故这种设计技巧的好处是i ≠ j和i = j分别对应偶数和奇数情况
• 然后主要函数就从头到尾以奇数个的情况匹一遍，偶数个的情况，选个最长的就行。

• Solution 2: Dynamic Programming
• 核心原理和Solution 1类似，但是可用DP（打表法）简化操作
• dp数组定义：dp(i, j) 表示s.substr(i, j)是否为回文串
• 比较容易的得到状态转移方程：

代码

class Solution {
public:
    string PalinDrome(string s, int left, int right){
        int len = s.length();
        while(left >= 0 && right < len && s[left] == s[right]){    
            left--;
            right++;
        }

        return s.substr(left + 1, right - left - 1);    //index changed at last time, so __pos = left + 1, __n = r - 1 - (l + 1) + 1
    }

    string longestPalindrome(string s) {
        string ans = "";
        int len = s.length();
        for(int i = 0; i < len; i++){
            //odds and evens
            int ansLen = ans.length();
            string tmpOdd = PalinDrome(s, i, i);
            string tmpEven = PalinDrome(s, i, i+ 1);

            // ans = tmpOdd.length() > ansLen ? tmpOdd : ans;
            if(ansLen < tmpOdd.length()){
                ans = tmpOdd;
            }
            if(ansLen < tmpEven.length()){
                ans = tmpEven;
            }
        }
        return ans;
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        int maxLen = 1, mLeft = 0;
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        if (s.size() == 1) {
            return s;
        }
        dp[n - 1][n - 1] = true;
        for (int i = 0; i < n - 1; i++) {
            dp[i][i] = true;
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;
                maxLen = 2;
                mLeft = i;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                if (s[i] == s[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    if (j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        mLeft = i;
                    }
                }
            }
        }
        return s.substr(mLeft, maxLen);
    }
};