Longest Palindromic Substring

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.

tag: string

9/23/2015 update

Same algorithm as described as follows, but neater I think.

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        string ans;
        for(int i = 0; i < len; i++){
            //i is the center of the possible palindromic substring
            int j = 0; //half length of the substring
            //odd palindrome
            while(i - j >= 0 && i + j < len && s[i - j] == s[i + j]){
                j++;
            }
            int substrlen = 2 * j - 1;
            ans = substrlen > ans.size()? s.substr(i - j + 1, substrlen): ans;
            
            //even palindrome
            j = 0;
            while(i - j >= 0 && i + j + 1 < len && s[i - j] == s[i + j + 1]){
                j++;
            }
            substrlen = 2 * j;
            ans = substrlen > ans.size()? s.substr(i - j + 1, substrlen): ans;
        }
        return ans;
    }
};

直接暴力搜，AC。
分成两种情况：回文子序列为奇数长度，回文子序列为偶数长度。
第一层循环确定回文的中心位置，第二层循环挨个尝试回文的长度。
需要注意的是在循环结束时，需要把halfLength–，因为循环结束时，halfLength停留在第一个不满足条件的元素位置。

用栈应该也能解决，就像parser一个语言一样。但没有细想，觉得复杂度应该和暴力差不多。

class Solution {
public:
    string longestPalindrome(string s) {
        string re;
        if (s.empty()){
            return re;
        }
        for(int mid = 0; mid < s.size(); mid++){//odd string
            int halfLength; 
            for(halfLength = 0; mid - halfLength >= 0 && mid + halfLength < s.size(); halfLength++){
                if(s[mid - halfLength] == s[mid + halfLength]){
                    continue;
                }
                else{
                    break;
                }
            }
            halfLength--;//don't forget this line. halfLength means first not acceptable substring before this line is executed
            if (halfLength * 2 + 1 > re.size()){
                re = s.substr(mid - halfLength, halfLength * 2 + 1);
            }
        }
        for (int leftMid = 0; leftMid + 1 < s.size(); leftMid++){//even string
            int halfLength;
            for(halfLength = 0; leftMid - halfLength >= 0 && leftMid + 1 + halfLength < s.size(); halfLength++){
                if(s[leftMid - halfLength] == s[leftMid + 1 + halfLength]){
                    continue;
                }
                else{
                    break;
                }
            }
            halfLength--;
            if (halfLength * 2 + 2 > re.size()){
                re = s.substr(leftMid - halfLength, halfLength * 2 + 2);
            }
        }
        return re;
    }
};