《每日一题》-最长回文子串

题目描述 T5

给定一个字符串s,找到s中最长的回文子串。示例1：

示例2：

题目解析

回文串有两种形式，因此需要考虑两种情况

长度为奇数，以中间字符对称，比如："bab"

长度为偶数，两端完全对称，没有中间字符，比如: "bb"

回文串既然是一种对称结构，那么可以从中间往两边进行扩展，扩展的过程中只需要满足两个条件即可继续扩展

小标合法 index>=0 && index

左右扩展的字符要相同 s[left] == s[right]

v1版本程序

根据上述思路，编写代码，代码如下：

提交程序后一次性通过，不幸的是只击败了1%的用户（思路没有错，写出来的程序为啥差距会这么大呢，发现新问题的小伙伴欢迎吐槽）。下面分析一下该程序的时间复杂度和空间复杂度：

时间复杂度

首先需要以任一字符作为中心进行扩展，每个字符扩展考虑两种情况，则执行2n次获取回文串的操作

获取回文串的操作，需要左右扩展，最坏的情况是扩展到字符串的边界，需要扩展n/2次 时间复杂度为 2n*n/2 = n^2

空间复杂度 使用了递归，每次递归最多递归n/2次，因为空间复杂度为O(n)

存在的不足

字符与字符串之间的转换比较多

递归可以改写为非递归

提前使用字符串保存了结果，实际上result与start和end记录了同类的信息，仅仅通过start和end即可获取到result，保留start和end即可

v2版本程序

时间复杂度仍然为o(n^2)由于递归修改为了非递归，因此空间复杂度为o(1)

不变的最后