【LeetCode】 5. Longest Palindromic Substring

Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

給一字串，找到它最長的屬於迴文的子字串。你可以假設字串最大長度只會有1000。

Example:

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.


Example 2:

Input: "cbbd"
Output: "bb"

Solution

• 使用DP，建一個表格存從哪裡到哪裡屬於迴文，然後往外推一個字，如果字是一樣，就更新表格。
• 其實這解法也是參考別人的寫法，不過寫出來速度並沒有到很快，不太確定要如何改善。

Code

class Solution {
public:
    string longestPalindrome(string s) {
        int size = s.size();
        
        if(size==0||size==1) return s;
        
        //make DP table and initialize
        vector<vector<int>> DP(size,vector<int>(size,1));
        for(int i=0;i<size;i++)
        {
            DP[i][i] = 1;
        }
        
        int maxLen = 0;
        int start = size - 1;
        int end = start;
        
        for(int i = 1;i<size;i++)
        {
            for(int j = 0,k = i;k<size;j++,k++)
            {
                if(s[j] == s[k] && DP[j+1][k-1])
                {
                    if(maxLen<k-j+1)
                    {
                        maxLen=k-j+1;
                        start=j;
                        end=k;
                    }
                    DP[j][k] = DP[j+1][k-1];
                }
                else
                    DP[j][k] = 0;
            }
        }
        
        string ans="";
        for(int i=start;i<=end;i++)
            ans+=s[i];
        return ans;
    }
};

tags: LeetCode C++