[c/c++]——最长回文子串「建议收藏」

[c/c++]——最长回文子串「建议收藏」最长回文子串已经很久没有更新关于leetcode的题解了,一个是觉得太费时间,二一个目前网上也有很全面的解答,但是在写leetcode的最长回文子串时,发现很多同学的代码都很长(实际上几行就可以解决的事情),并且c++解答的代码不够完整。最关键的是在一种“马拉车”的算法卡了很久很久,今天把几种求解的方法全部都整理出来,方便大家也便于自己以后复习。ps:讲解很少,都是整理出可看性很高的源码方法…

大家好,又见面了,我是你们的朋友全栈君。

最长回文子串

已经很久没有更新关于leetcode的题解了,一个是觉得太费时间,二一个目前网上也有很全面的解答,但是在写leetcode的最长回文子串时,发现很多同学的代码都很长(实际上几行就可以解决的事情),并且c++解答的代码不够完整。最关键的是在一种“马拉车”的算法卡了很久很久,今天把几种求解的方法全部都整理出来,方便大家也便于自己以后复习。

ps:讲解很少,都是整理出可看性很高的源码

方法一:暴力求解

其实在做多了leetcode的题之后你会发现,你拿到题如果第一想法是暴力解法那么恭喜你,95%过不了,所以这里的第一种暴力法如果在面试时被问到你可以讲出来为后面更优秀的算法做铺垫,实际上没有什么使用价值,这道题领扣只过了60%用例左右吧

  • 时间复杂度:O(N^3)
  • 空间复杂度:O(1)
  • 思路:思路很简单,双循环判断每一个从i开始到j结束的子串是不是回文的,因为判断子串又需要遍历一遍所以时间复杂度为O(N^3)
class Solution { 
   //暴力算法
public:
    string longestPalindrome(string s) { 
   
        if(s.size() == 0 || s.size() < 2) return s;
        int max = 0;
        string ret = "";
        for(int i = 0;i < s.size();i++)
        { 
   
            for(int j = 1;j < s.size();j++)
            { 
   
                string tmp = s.substr(i,j-i+1);
                string tmpr(tmp);//这里将这个子串反转一下与原串对比是否相同
                reverse(tmp.begin(),tmp.end());
                if(tmp == tmpr && tmp.size() > max)
                { 
   
                    max = tmp.size();
                    ret = s.substr(i,j-i+1);
                }
            }
        }
        return ret;
    }
};

方法二:中心扩散算法

这个算法相对暴力算法来说可以说效率高了不只一点点,甚至比动态规划还要好。

  • 时间复杂度:O(N^2)
  • 空间复杂度:O(1)
  • 思路:以abbba为例子,我们以最中间的b为例子,向两边扩散为bbb -> abbba,结束。当然如果是abba的字符串我们就可能需要从bb开始扩散bb -> abba结束,思路并不难理解照着源代码就能豁然开朗。(其实很好理解,不要觉得很难因为硬菜在后面,嘿嘿嘿)
class Solution { 
   //中心扩散法
public:
    int max = 0;
    string ret = "";
    void spread(string& s,int left,int right) { 
   
        int L = left,R = right;
        while(L >= 0 && R < s.size() && s[L] == s[R]) { 
   //向左向右扩散
            if(R-L+1 > max) { 
   
                max = R-L+1;
                ret = s.substr(L,R-L+1);
            }
            L--; R++;
        }
    }
    string longestPalindrome(string s) { 
   
        if(s.size() <= 1) return s;
        for(int i = 0;i < s.size();i++) { 
   
            spread(s,i,i);//从单个字符开始扩散
            spread(s,i,i+1);//从相邻的两个字符开始扩散
        }
        return ret;
    }
};

方法三:动态规划

如果你没有学过动态规划的思想可以先了解下什么是动态规划,动态规划在这道题中效率出奇的低这让人也是很纳闷

  • 时间复杂度:O(N^2)
  • 空间复杂度:O(N^2)
  • 思路:一个子串是否为回文串可以判断这个子串的第一个与最后一个是否相等+中间的子串是否为回文,中间的子串又可以分解为第一个与最后一个是否相等+中间的子串是否为回文,所以我们就找到了最优子结构,我们直接贴代码来分析
class Solution { 
   //动态规划
public:
    string longestPalindrome(string s) { 
   
        if(s.size() == 0) return s;
        int dp[s.size()][s.size()] = { 
   0};//创建一个存放状态的数组
        string ret = "";
        int max = 0;
        for(int i = 0;i < s.size();i++) { 
   //这个双循环是在判断i到j位置的子串是否为回文串
            for(int j = 0;j <= i;j++) { 
   
                dp[i][j] = s[i] == s[j] && (i-j <=2 || dp[i-1][j+1]);
                //i-j <=2这句是因为如果子串为bb时就是极限状态,他也构成回文
                //dp[i-1][j+1]这句就是判断中间的子串是否为回文,很好理解
                if(dp[i][j]) { 
   
                    if(i-j+1 > max) { 
   
                        max = i-j+1;
                        ret = s.substr(j,i-j+1);
                    }
                }
            }
        }
        return ret;
    }
};

方法四:马拉车算法

在这里插入图片描述
真是个让人头皮发麻的算法,说真的,我也讲不清楚,有时候我脑子里明白的东西我说出来大家可能还是一脸懵逼,就把自己找到非常优秀的讲解给大家贴上,嘤嘤嘤,这样大家就可以少走点弯路找资料了。

链接:https://www.felix021.com/blog/read.php?2040
(多的不贴了,这个讲的真的是最好的,其余的都是把人家的抄过来,很多博客笔者可能自己都没明白)

我这里就说一些细节(给大家用大白话讲出来)的东西,帮助大家更好的理解,前提确保你先真正看懂了如何求解p数组

class Solution { 
   //马拉车算法
public:
    string longestPalindrome(string s) { 
   
        if(s.size() <= 1) return s;
        string str = "@#";//一定注意这个@,非常关键,因为在从下标为1的#字符开始求解p数组时没有这个符号就越界了
        for(int i = 0;i < s.size();i++) { 
   
            str += s[i];
            str += '#';
        }
        
        vector<int> p(str.size(),0);
        int mx = 0, id = 0,start = 0,maxlen = 0;
        for (int i = 1; str[i] != '
class Solution { 
//马拉车算法
public:
string longestPalindrome(string s) { 

if(s.size() <= 1) return s;
string str = "@#";//一定注意这个@,非常关键,因为在从下标为1的#字符开始求解p数组时没有这个符号就越界了
for(int i = 0;i < s.size();i++) { 

str += s[i];
str += '#';
}
vector<int> p(str.size(),0);
int mx = 0, id = 0,start = 0,maxlen = 0;
for (int i = 1; str[i] != '\0'; i++) { 

//这里如果i在右边界mx之外就只能自己老实匹配了,如果在mx之内需要看p[j]是否大于对称的mx左边界,大于的话说明i位置
//的p[i]至少也能延展到以id为中心的回文边界,否则只能是p[j]的值
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
while (str[i + p[i]] == str[i - p[i]]) p[i]++;
if (i + p[i] > mx) { 

mx = i + p[i];
id = i;
}
if(p[i]-1 > maxlen)
{ 

start = (i-p[i])/2;//i+p[i]是右边界,所以i-p[i]就是左边界,除以2是因为str加了#变成了两倍长度,所以
//在原串的开始位置就是除以2
maxlen = p[i]-1;
}
}
return s.substr(start,maxlen);
}
};
'
; i++) { //这里如果i在右边界mx之外就只能自己老实匹配了,如果在mx之内需要看p[j]是否大于对称的mx左边界,大于的话说明i位置 //的p[i]至少也能延展到以id为中心的回文边界,否则只能是p[j]的值 p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1; while (str[i + p[i]] == str[i - p[i]]) p[i]++; if (i + p[i] > mx) { mx = i + p[i]; id = i; } if(p[i]-1 > maxlen) { start = (i-p[i])/2;//i+p[i]是右边界,所以i-p[i]就是左边界,除以2是因为str加了#变成了两倍长度,所以 //在原串的开始位置就是除以2 maxlen = p[i]-1; } } return s.substr(start,maxlen); } };

文章主要以总结c++代码为主,理解还需大家自己体会,有什么问题尽管指出我会虚心改正。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/134395.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • static静态变量在内存中的存储[通俗易懂]

    static静态变量在内存中的存储[通俗易懂]static用来控制变量的存储方式和可见性    函数内部定义的变量,在程序执行到它的定义处时,编译器为它在栈上分配 空间,函数在栈上分配的空间在此函数执行结束时会释放掉,这样就产生了一个 问题:如果想将函数中此变量的值保存至下一次调用时,如何实现?最容易想 到的方法是定义一个全局的变量,但定义为一个全局变量有许多缺点,最明显的 缺点是破坏了此变量的访问范围(使得在此函数中定义的变量,不仅…

  • Go Modules 详解

    Go Modules 详解

  • 用fread函数或fwrite函数读写的文件必须是_FCGI_fwrite

    用fread函数或fwrite函数读写的文件必须是_FCGI_fwritefwrite和fread是以记录为单位的I/O函数,fread和fwrite函数一般用于二进制文件的输入输出。#includesize_tfread(void*ptr,size_tsize,size_tnmemb,FILE*stream);size_tfwrite(constvoid*ptr,size_tsize,size_tnmemb,FILE*s

  • Spring使用JPA进行Dao层的数据访问以及事务管理

    Spring使用JPA进行Dao层的数据访问以及事务管理

  • leetcode-150. 逆波兰表达式求值(栈)

    leetcode-150. 逆波兰表达式求值(栈)根据 逆波兰表示法,求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。说明:整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。 示例 1:输入:tokens = [“2″,”1″,”+”,”3″,”*”]输出:9解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9示例 2:输入:tokens = [“4″,”13″,”5″,”/”,”+”]输

  • 机器学习框架简述

    机器学习框架简述机器学习框架意味着一个能够整合包括机器学习算法在内的所有机器学习的系统或方法,使用户最有效的使用它们。具体来讲,这包括数据表示与处理的方法、表示和建立预测模型的方法、评价和使用建模结果的方法。在所有可用的机器学习框架中,着重于迭代算法和交互处理的框架被公认为是最好的,因为这些特性可以促进复杂预测模型估计和研究人员与数据间的良好交互。当下,优秀的机器学习框架依旧需要包含大数据功能…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号