leetcode 5: longest palindrome subarray

 leetcode 5:  longest palindrome subarray

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

思路： 找到最长回文子串， 首先想到的是需要把所有可能的回文都找出来，update长度最长的一个，问题转化到如何把一个字符串里面所有的回文子串都找出来，对于panlindrome的求法，有3种，1.利用递归，两头的char是否相等，然后看去掉两头的字符串是不是回文 2. 利用DP， 二维矩阵，M[i][j]代表string from index i to index j is palindrome or not.  M[i][j]依赖于M[i+1][j-1]。 3. 利用两个指针从中间往两边进行scan， 到不相等时，即此时的string 不是palindrome。 方法三是最好的，时间复杂度o(n^2), 空间复杂度o(1). 

class Solution {
//use dp to find palindromes
//update the max length of the palindorome
public:
    string longestPalindrome(string s) {
        //sanity check
        if (s.size() == 0) return s;
        //M[i][j] represent if substring from i to i+j is palindrome or not
       
       bool M[s.size()][s.size()];
        //base case
        for (int i = 0; i < s.size(); i++) {
            M[i][i] = true;
        }
        int max_len = 0;
        int start = 0;
        int end = 0;
        for (int j = 1; j < s.size(); j++) {
            for (int i = 0; i+j < s.size(); i++) {
                if (s[i] == s[i+j] && (j == 1 || M[i+1][i+j-1])) { //if the start and end char is the same
                     M[i][j+i] = true;
                     if (max_len < j) {
                        max_len = j;
                        start = i;
                        end = i+j;
                    }
                }else M[i][j+i] = false;
            }
        }
        return s.substr(start, end-start+1);
    }
};