By

版权声明：本文章为博主原创，转载请注明出处。保留所有权利。

Contents
  1. 1. 题目
  2. 2. 解析

Leetcode-5的解题过程。

  • 题目

    Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
    Example:
    Input: “babad”
    Output: “bab”
    Note: “aba” is also a valid answer.

    1
    2
    3
    Example:
    Input: "cbbd"
    Output: "bb"

  • 解析

    查找最长回文子串，一道比较经典的字符串处理题目。对于一个长度为n的字符串来说，所有可能的子串有2^n种，想全部遍历显然是不现实的，我们需要一种更加高效的办法来扫描字符串。我们的目标是要找到回文字符串，所以可以根据回文串的特点来进行查找。回文串可以分为两类：

  • 长度为奇数，这样的回文串会有一个中心字符，其他的字符都关于这个字符对称
  • 长度为偶数，这两的回文串的中心字符有两个且必定相同，其他字符都关于这两个字符对称
    那么我们可以逐个字符扫描原字符串s，并将当前的字符（或当前字符与其下一个字符）作为假想的回文串中心字符，并以此为起点，比对s中关于假想中心对称位置的字符，来找到候选的回文串，如图所示。
    奇数情况
    偶数情况

总的来说这道题也不是很难，要注意的是一些边界情况以及奇数和偶数的讨论。

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
48
49
50
51
52
53
54
55
56
57
58
class Solution(object):
    def isPalindromic(self, s):

        head = 0
        tail = len(s) - 1
        while (head < tail):
            if s[head] != s[tail]:
                return False
            head += 1
            tail -= 1
        return True
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if self.isPalindromic(s):
            return s
        i = 0
        l = len(s)
        maxlen = 0
        h = 0
        t = l
        while (i < l):
            head = i
            tail = i
            flag = False
            thislen = 0
            while head >= 0 and tail < l and head <= tail:
                if s[head] != s[tail]:
                    flag = False
                    break
                thislen = tail - head+1
                if thislen > maxlen:
                    maxlen = thislen
                    h = head
                    t = tail
                head -= 1
                tail += 1

                # flag = True
            head = i
            tail = i + 1
            while head >= 0 and tail < l and head <= tail:
                if s[head] != s[tail]:
                    flag = False
                    break
                thislen = tail - head +1
                if thislen > maxlen:
                    maxlen = thislen
                    h = head
                    t = tail
                head -= 1
                tail += 1

            i += 1

        return s[h:t+1]

打赏

取消
扫码支持

你的支持是对我最好的鼓励

Contents
  1. 1. 题目
  2. 2. 解析