leetcode Longest Palindromic Substring(动态规划求解最长回文子串)

深碍√TFBOYSˉ_ 2022-03-17 09:27 237阅读 0赞

[https://leetcode.com/problems/longest-palindromic-substring/][https_leetcode.com_problems_longest-palindromic-substring]

题意：求最长回文子串

思路：动态规划，设dp\[i\]\[j\]表示从i到j的子串是不是回文串，如果是dp\[i\]\[j\]=1,否则dp\[i\]\[j\]=0.

状态转移：dp\[i\]\[j\]=dp\[i+1\]\[j-1\]&&s\[i\]==s\[j\]。

注意边界条件。

需要逆序遍历，因为我们的状态转移是向外扩展的。

代码：

#include <bits/stdc++.h>
    using namespace std;
    class Solution {
    public:
        string longestPalindrome(string s) {
            int dp[1005][1005];
            memset(dp,0,sizeof(dp));
            int n=s.size();
            if(n==1){
                return s;
            }
            int M=1;
            int l=0,r=0;
            for(int i=0;i<n;i++) dp[i][i]=1;
            for(int i=n-1;i>=0;i--)
            {
                for(int j=i+1;j<n;j++)
                {
                    if(i<n-1)
                    {
                        if(j>0)
                        {
                            if(s[i]==s[j])
                            {
                                if(i+1==j) dp[i][j]=1;
                                else if(dp[i+1][j-1]){
                                    dp[i][j]=dp[i+1][j-1];
                                }
    
                            }
    
                        }
                    }
                    if(dp[i][j]&&M<(j-i+1))
                    {
                        M=j-i+1;
                        l=i,r=j;
                    }
                }
            }
            string ans;
            for(int i=l;i<=r;i++)
            {
                ans.push_back(s[i]);
            }
            return ans;
        }
    };

[https_leetcode.com_problems_longest-palindromic-substring]: https://leetcode.com/problems/longest-palindromic-substring/