Simple C++ DP solution (Accepted)


  • 0
    V
    class Solution {
    public:
        string longestPalindrome(string s) {
            if (s.length() == 0 || s.length() == 1)
                return s;
    
            vector<vector<int>> dp(s.length(), vector<int>(s.length()));        
            for (int i=0; i<s.length(); i++)
                dp[i][i] = 1;
            
            int maxLen = 1;
            for (int L=2; L<=s.length(); L++) {
                for (int i=0; i<s.length()-L+1; i++) {
                   int j = i+L-1;
                    if (s[i] == s[j] && L == 2)
                        dp[i][j] = 2;
                    else if (s[i] == s[j] && dp[i+1][j-1] > 0)
                        dp[i][j] = dp[i+1][j-1] + 2;
                    else
                        dp[i][j] = 0;
                    
                    maxLen = max(maxLen, dp[i][j]);
                }
            }
            
            int start = 0;
            for (int i=0; i<s.length(); i++) {
                for (int j=i; j<s.length(); j++) {
                    if (dp[i][j] == maxLen) {
                        start = i;
                        break;
                    }
                }
            }   
            return s.substr(start, maxLen);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.