Leetcode.5. Longest Palindromic Substring

题目

给定一个字符串, 找出最长的对称子字符串, 例如aba, abba, aaaa.

Example:
Input: "babad"
Output: "bab"

Input: "cbbd"
Output: "bb"

思路1

时间复杂度: O(nnn)

循环遍历出所有子字符串, 判断子字符串的对称性.

string longestPalindrome(string s) {
    int count = 0;
    string result = s.substr(0,1);
    int len = (int)s.size();

    for (int i=0; i<s.size(); i++) {
        char ch = s[i];
        for (int j=len-1; j>=i; j--) {
            char x = s[j];
            if (ch == x) {
                bool isOK = true;
                for (int k=1; k<=(j-i)/2; k++) {
                    if (s[i+k] != s[j-k]) {
                        isOK = false;
                        break;
                    }
                }
                if (isOK && j-i+1 > count) {
                    result = s.substr(i,j-i+1);
                    count = (int)result.size();
                }
            }
        }
    }
    return result;
}

思路2

时间负责度: O(n*n)

针对每一个字符, 从中间向两边扩展, 找到每个字符的最大对称字符串.

int expandPalindrome(string s, int left, int right) {
    int l = left, r = right;
    int len = (int)s.size();
    while (l >= 0 && r < len && s[l] == s[r]) {
        l--;
        r++;
    }

    return r - l - 1;
}

string longestPalindrome(string s) {
    int start = 0, end = 0, len = 0;
    for (int i = 0; i < s.size(); i++) {
        int len1 = expandPalindrome(s, i, i);
        int len2 = expandPalindrome(s, i, i+1);
        int tempLen = max(len1, len2);
    
        if (tempLen > end - start) {
            len = tempLen;
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substr(start, len);
}