Leetcode. P5 最长回文子串

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
Input: "cbbd"
Output: "bb"

动态规划过程推导，可以参考链接
在实现的时候，容易犯的错是，在构建动态规划二维数组的时候，注意计算的顺序，因为计算时有前置依赖项。
在下面的实现中，关键点就是k的含义，即当前所判断的子串最大长度。
而本题中的前置依赖，就是 k - 2 长度的子串是否为回文子串。
所以在构建二维数组的时候，需要子串长度由短到长来判断。

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() == 0 || s.size() == 1)
        {
            return s;
        }
        int len = s.size();
        bool a[len][len];
        int maxLen = 0;
        int startMax = 0;
        for (int i = 0; i < len; ++i)
        {
            a[i][i] = true;
        }
        for (int i = 0; i < len -1; ++i)
        {
            a[i][i + 1] = s[i] == s[i+1];
        }
        for (int k = 2; k < len; ++k)
        {
            for (int i = 0, j = k; j < len; ++i, ++j)
            {
                a[i][j] = s[i] == s[j] ? a[i+1][j-1] : false;
            }
        }
        for (int i = 0; i < len; ++i)
        {
            for (int j = i; j < len; ++j)
            {
                if (a[i][j])
                {
                    if (j - i + 1 > maxLen)
                    {
                        maxLen = j - i + 1;
                        startMax = i;
                    }
                }
            }
        }
        return s.substr(startMax, maxLen);
    }
};