欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 5. Longest Palindromic Substring (DP)

程序员文章站 2024-03-23 11:27:28
...

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

Example 1:

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

Example 2:

Input: "cbbd"
Output: "bb"

注意边界条件,如没有回文串。

class Solution {
    int dp[1002][1002];
public:
    string longestPalindrome(string str) {
       int n =str.size(); 
       for(int i=0;i<n;i++)
            dp[i][i] = 1;
       int s=0, l = 0;
       for(int j=1;j<n;j++)
           for(int i=0;i<j;i++) {
               if(str[i]==str[j]) {
                   if(j==i+1) dp[i][j]=1;
                   else
                       dp[i][j]=dp[i+1][j-1];
                   if(dp[i][j] && (j-i+1) >= l) {
                       l = j-i+1;
                       s = i;
                   }
               }
           }
        if(l==0) return str.substr(0, 1);
        return str.substr(s, l);
    }
};
相关标签: DP LeetCode