最长回文子串(leetcode5)

小咪咪 2023-06-03 14:53 11阅读 0赞

求一个字符串的最长回文子串，我们可以将以每个字符为首的子串都遍历一遍，判断是否为回文，如果是回文，再判断最大长度的回文子串。算法简单，但是算法复杂度太高，O（n^3）

string longestPalindrome(string s)
     {
         if(s.empty()) return "";
         if(s.size()==1) return s;
         int start=0,maxlength=1;//记录最大回文子串的起始位置以及长度
         for(int i=0;i<s.size();i++)
             for(int j=i+1;j<s.size();j++)//从当前位置的下一个开始算
             {
                 int temp1,temp2;
                 for(temp1=i,temp2=j;temp1<temp2;temp1++,temp2--)
                 {
                     if(s[temp1]!=s[temp2])
                         break;
                 }
                 if(temp1>=temp2 && j-i+1>maxlength)//这里要注意条件为temp1>=temp2，因为如果是偶数个字符，相邻的两个经上一步会出现大于的情况
                 {
                     maxlength = j-i+1;
                     start=i;
                 }
             }
        return s.substr(start,maxlength);//利用string中的substr函数来返回相应的子串,第一个参数是起始位置，第二个参数是字符个数
     }

动态规划

string longestPalindrome(string s)
    {
        //dp 时间O(n^2)空间O(n^2)
        //f(i,j) dp[i][j]=1=>Si...Sj是回文
        // f(i,j) = true, i=j
        // f(i,j) = S[i]=S[j], j=i+1
        // f(i,j) = S[i]=S[j] and f(i+1,j-1), j>i+1
        if(s.empty())
            return "";
        int len = s.size();
        if(len == 1)
            return s;
        int longest = 1; //记录回文最大长度
        int start = 0; //记录回文开始位置
        vector<vector<int>> dp(len,vector<int>(len,0)); //初始化二维数组为0
        //相同字母长度为2
        for(int i = 0;i < len;i++)
        {
            dp[i][i] = 1; //二维数组对角线设为1
            if(i<len)
            {
                if(s[i] == s[i+1])
                {
                    dp[i][i+1] = 1;
                    start = i;
                    longest = 2;
                }
            }
        }
        //从长度3开始 遍历长度
        for (int lon = 3; lon <= len; lon++)
        {
            //从初始位置开始依次遍历当前长度的子串，确认其中是否有回文子串
            for (int i = 0; i+lon-1 < len; i++) //枚举子串的起始点
            {
                int end = lon+i-1; //终点
                if (s[i] == s[end] && dp[i+1][end-1] == 1)
                {
                    dp[i][end] = 1;
                    start = i;
                    longest = lon;
                }
            }
        }
        return s.substr(start,longest);
    }

# Manacher算法（马拉车算法） #

string longestPalindrome(string s)
    {
        if (s.empty()) return "";
        int len = s.size();
        if (len == 1)return s;
        int longest = 1;
        int start=0;
        vector<vector<int> > dp(len,vector<int>(len));
        for (int i = 0; i < len; i++)
        {
            dp[i][i] = 1;
            if(i<len-1)
            {
                if (s[i] == s[i + 1])
                {
                    dp[i][i + 1] = 1;
                    start=i;
                    longest=2;
                }
            }
        }
        for (int l = 3; l <= len; l++)//子串长度
        {
            for (int i = 0; i+l-1 < len; i++)//枚举子串的起始点
            {
                int j=l+i-1;//终点
                if (s[i] == s[j] && dp[i+1][j-1]==1)
                {
                    dp[i][j] = 1;
                    start=i;
                    longest = l;
                }
            }
        }
        return s.substr(start,longest);
    }

转载于:https://www.cnblogs.com/didiaoxiaoguai/p/10870826.html