[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] != '\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);
    }
};

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

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

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

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

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

(0)


相关推荐

  • java 自定义的类加载器_Java如何自定义类加载器[通俗易懂]

    java 自定义的类加载器_Java如何自定义类加载器[通俗易懂]我们可以编写自己的用于特殊目的的类加载器,这使得我们可以在向虚拟机传递字节码之前执行定制的检查。如何自定义类加载器如果想要编写自己的类加载器,只需要两步:继承ClassLoader类覆盖findClass(StringclassName)方法ClassLoader超类的loadClass方法用于将类的加载操作委托给其父类加载器去进行,只有当该类尚未加载并且父类加载器也无法加载该类时,才调用fin…

  • 测试用例编写_功能测试用例自动生成

    测试用例编写_功能测试用例自动生成前言写用例之前,我们应该熟悉API的详细信息。建议使用抓包工具Charles或AnyProxy进行抓包。har2case我们先来了解一下另一个项目har2case他的工作原理就是将当前主流的抓

  • datax(13):源码解读Column-datax中的数据类型

    datax(13):源码解读Column-datax中的数据类型一、基类Column概述Column是datax中所有数据类型的基类,里面有3个属性,以及一个构造方法,外加一个枚举类;publicabstractclassColumn{ privateTypetype; privateObjectrawData; privateintbyteSize; publicColumn(finalObjectobject,finalTypetype,intbyteSize){ this.rawData=objec

  • python格式化输出之format用法

    python格式化输出之format用法format用法相对基本格式化输出采用‘%’的方法,format()功能更强大,该函数把字符串当成一个模板,通过传入的参数进行格式化,并且使用大括号‘{}’作为特殊字符代替‘%’使用方法由两种:b

  • Freeswitch+webSocket 尝试开发呼叫中心工具条actionbar 成功小结

    Freeswitch+webSocket 尝试开发呼叫中心工具条actionbar 成功小结好久没有写文章,因为我在酝酿大招。^_^呼叫中心工具条开发环境:LinuxCentos6.x+java1.8+websocket+Freeswitch1.5+API(提供其他语言调用工具条,不仅限于java)1、来电弹屏(DEMO演示了一个客户表,通过来电号码判断查询用户,并展示给坐席)2、电话状态变化提示 ringing,answer,han

发表回复

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

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