LeetCode05最长回文子串

发表于 | 更新于 | 分类于 |

题目描述：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

感悟：

  1. 一定要审好题。。。一开始想当然的认为自己理解了什么是回文子串。其实理解错误，然后再重头开始做，浪费时间。所以，一定要明白自己在做什么。
  2. 要灵活，想问题要灵活，换个角度来思考一下，有没有更容易的解决办法，可以类比一下。关于算法问题，常用的几类解题方法更要稔熟于心。具体的多看别人总结的知识，学习别人的知识，总比自己瞎想要系统，要全面，当然如果自己不去思考，那也白看。(1) https://blog.csdn.net/int1282951082/article/details/52128991 (2) https://www.cnblogs.com/ganhang-acm/p/3860361.html
  3. 在LeetCode上面，有解答的问题，一定要看一下别人的解答。先自己思考怎么做，然后再看别人的解题思路。

解题思路：

一开始我的解题思路就是暴力做。

  1. 固定起始字符，选择首尾字符相同的最大字符串，然后判断其是不是回文串，如果是，与最大length比较，比之大的话，则更新最大length和相应的串结果result
  2. 上一步固定起始字符，获得的最大字符，如果不满足的话，则选择第二大的字符，继续判断。
  3. 然后再继续固定下一个字符，继续循环。

中间可以加入停止状态，当剩余串长度小于最大length的时候，就可以停止了。当然这个办法是非常耗时的，尤其是判断是否是回文字符串时。

额…. 就在刚才，写着写着，突然想起来，好像可以改进一下判断方法，结果，提交之后通过了。之前一直是超时状态。

原来判断是回文字符串的方法是：

1
2
3
4
5
6
7
def judge(str):
    mean = int((len(str) + 1) / 2)

    for i in range(mean):
        if str[i] != str[len(str) - 1 - i]:
            return False
    return True

其实，只要将字符串倒序一下，然后判断是否相同即可。。。唉

1
2
3
4
5
6
7
def judge2(str):

    s2 = str[::-1]
    if s2 == str:
        return True
    else:
        return False

另一种思路：

当然，这题可以从另外的角度来做。

比如说，先将字符串倒序，然后寻找两字符串最大公共子串。这个方法应该挺常用的。

寻找最大公共子串的主要思路就是用一个矩阵，将两个字符串分别作为行和列，简单画个图表示就是：

用矩阵记录字符串相等的情况，矩阵某位置的值 = 左上角 + 1(如果相同，否则为0)

在得到最大公共子串之后，则可以继续判断公共子串的起始位置，在原始的两字符串中是否一样，如果一样的话，则说明找到了回文串，如果不一样的话，需要再找第二大的公共子串，重复该过程。

代码实现：

GitHub地址：https://github.com/zhangdianlei/LeetCode_python/blob/master/src/c05.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
def judge(str):

    s2 = str[::-1]
    if s2 == str:
        return True
    else:
        return False


class Solution:

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        result = ""
        if len(s) == 0:
            return result
        else:
            length = 0

            for index, item in enumerate(s):

                endIndex = s.rfind(item)

                while endIndex != -1:
                    tempStr = s[index:endIndex + 1]

                    if judge(tempStr):

                        if (endIndex - index + 1) > length:
                            length = endIndex - index + 1
                            result = s[index:endIndex + 1]

                            if length >= len(s) - index:
                                return result
                            break

                    endIndex = s.rfind(item, 0, endIndex)

                if endIndex == -1:
                    if length == 0:
                        result = item
                        length = 1

            return result