【LeetCode】最长回文子串【动态规划或中心扩展】

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring

方法1：动态规划

最优子结构：当一个串是一个回文串的时候，在其头尾各加一个相同的字符组成的新字符串依旧是一个回文串

dp[i][j]=1，代表从下标i到下标j组成的字符串是一个回文串

如果s[i]==s[j]&&dp[i+1][j-1]==1，那么dp[i][j]=1

初始化：

1.对于一个字符的回文串：dp[i][i]=1

2.对于两个字符的回文串：如果s[i]==s[i+1]，那么dp[i][i+1]=1

对于三个字符的回文串：如果s[i]==s[j]&&dp[i+1][j-1]==1，那么dp[i][j]=1

时间复杂度：O(N^2)

空间复杂度：O(N^2)

class Solution {

public:

string longestPalindrome(string s)

{

    if(s.size()==)

        return "";

    if(s.size()==)

        return s;

    if(s.size()==&&s[]==s[])

        return s;

    int n=s.length();

    int dp[n+][n+];

    memset(dp,,sizeof(dp));

    int ans=;

    int start=;

    for(int i=;i<n;i++)

    {

        dp[i][i]=;

    }

    for(int i=;i<n-;i++)

    {

        if(s[i]==s[i+])

        {

            dp[i][i+]=;

            ans=;

            start=i;

        }

    }

    int l=;

    while(l<=n)

    {

        for(int i=;i<n-l+;i++)

        {

            int j=i+l-;

            if(dp[i+][j-]==&&s[i]==s[j])

            {

                dp[i][j]=;

                start=i;

                ans=l;

            }

        }

        l++;

    }

    return s.substr(start,ans);

}

};

方法2：中心扩展法

将每个字符当作回文串的中心，然后往两边扩展，取扩展得到的回文串的最大值就是最长回文子串

考虑到回文串的奇偶情况，我们可以算两种情况：以一个字符为回文串的中心，以两个字符为回文串的中心，然后去二者最大值就可以

时间复杂度：O(N^2),以每个字符为中心需要遍历一次，然后每次都需要往两边扩展

空间复杂度：O(1),只需要用到一些常量

class Solution {

public:

int f1(string str,int left,int right,int n)

{

    int c=;

    //cout<<"left="<<left<<" right="<<right<<" n="<<n<<endl;

    left--;

    right++;

    while(left>=&&right<n&&str[left]==str[right])

    {

        left--;

        right++;

        c+=;

    }

    return c;

}

int f2(string str,int left,int right,int n)

{

    int c=;

    if(str[left]==str[right])

        c=;

    else

    {

        c=;

        return c;

    }

    left--;

    right++;

    while(left>=&&right<n&&str[left]==str[right])

    {

        left--;

        right++;

        c+=;

    }

    return c;

}

string longestPalindrome(string s)

{

    int n=s.size();

    if(n==)

        return "";

    if(n==)

        return s;

    if(n==&&s[]==s[])

        return s;

    int ans=;

    int start=;

    for(int i=;i<n-;i++)

    {

        int x1=f1(s,i,i,n);

        int x2=f2(s,i,i+,n);

        //cout<<"i="<<i<<" x1="<< x1<<" x2="<<x2<<endl;

        if(max(x1,x2)>ans)

        {

            ans=max(x1,x2);

            //cout<<"ans="<<ans<<endl;

            if(ans%==)

                start=i-ans/;

            else

                start=i-(ans-)/;

            //cout<<"start="<<start<<endl;

        }

    }

    return s.substr(start,ans);

}

};

还有一个解决方案是马拉车算法

时间复杂度为O(N)!!!

但是我目前也没有掌握，就没有贴出来，怕误导别人

巴特西

【LeetCode】最长回文子串【动态规划或中心扩展】

最新文章

热门文章