原题给定字符串，找到它的最长回文子串，都有哪些思路呢？例如"adaiziguizhongrenenrgnohziugiziadb",回文字串很多了，但最长的是"daiziguizhongrenenrgnohziugiziad"。 分析这是一个十分经典的题目，方法也很多。下面我们在介绍的时候，不会每个方法都很详细的介绍，不过同学们在练习的时候需要每个方法都写一下，进而才能够举一反三。 第一个方法当然是暴力法，外面的两层循环找到所有子串，第三层循环判断子串是否是回文。方法的时间复杂度为O(n^3)，空间复杂度为O(1)。 第二个方法，采用的是动态规划的方法。开辟一个P[i][j]用来表示str[i..j]是否为回文，P[i][j]的状态转移方程如下：
|
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
