Monday, November 24, 2014

[LeetCode] 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.

思路:

一开始觉得是一维DP。dp[i]记录以i为结尾的最长回文的长度,然后有通项公式:

dp[i] = dp[i-1] + 2,如果s[i] = s[j],j = i - dp[i-1] - 1。否则为dp[i] = 1

例如:a b c b a d
p[3] = 3 && s[4] = s[0] => dp[4] = 5

但是仔细一想,当s[i] != s[j]时,dp[i]实际是无法确定的。

例如:b a c c a c
dp[4] = 4 (a c c a),但s[5] != s[0],而实际dp[5] = 3因为s[5] = s[3],且s[4:4]是回文。

因此这题不是简单的一维DP,而是二维DP,需要计算并记录任意s[i:j]是否是回文:

定义bool isPal[i][j]表示s[i:j]是否为回文,isPal[i][j] = true需要满足两个条件: 
1. s[i] ==s[j]
2. i+1>j-1或 isPal[i+1][j-1] == true (即s[i+1 : j-1]是回文)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()<=1) return s; 
        int start = 0, maxLen = 1, n = s.size();
        bool isPal[1000][1000] = {false};
        
        for(int i=n-1; i>=0; i--) {
            for(int j=i; j<n; j++) {
                if((i+1>j-1 || isPal[i+1][j-1]) && s[i]==s[j]) {
                    isPal[i][j] = true;
                    if(j-i+1>maxLen) {
                        maxLen = j-i+1;
                        start = i;
                    }
                }
            }
        }
        
        return s.substr(start,maxLen);
    }
};

1 comment: