Leetcode 5: Longest Palindromic Substring

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 853 | 阅读时长 ≈ 1 分钟

出处

源自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:

1
2
3
Input: "babad"

Output: "bab"

Note: “aba” is also a valid answer.

Example:

1
2
3
Input: "cbbd"

Output: "bb"

解读

给定字符串s, 找到最长回文子串，可以假设s的最长长度为1000
给定两个例子

  • babad的最长回文子串为bab（aba也是，给定一个即可）
  • cbbd的最长回文子串为bb

第一个解法

思路

  1. 遍历s，以当前字符为中心节点，往两边拓展
  2. 如果左边字符和右边字符一样，则继续拓展
  3. 否则拓展结束，记录下最长子串

缺点

由于同时往两边拓展，所以例子2中的情形无法处理（回文子串长度为偶数的无法处理）， 可以加上补丁算法，处理偶数情形，但是比较复杂，不予讨论，引入下一种思路：

第二个解法

思路

第一个思路是由中间往两边拓展，处理奇数和偶数长度子串要分别处理，由于回文子串的边界字符肯定相等，如果可以相同字符为边界，往里拓展

  1. 找到两个相等的字符，以之为边界(下边界和上边界)，进行步骤2
  2. 如果上、下边界相等，则为回文字符，否则上边界减1、下边界加1，继续步骤2

综上所示，可以利用一个记忆数组的方法，s的字符串长度为n，设置一个n*n的记忆数组，记忆(i, j)是否为回文，每次以相等字符为边界，往内部推进，判断(i-1, j+1)是否为回文，并且记忆结果，已备下次查询使用；

  1. 统计s中每个单词出现的位置
  2. 取出同样的单词出现的位置并设为judge(i, j)，
  3. 判断i - 1位置的单词是否和j - 1处的单词一样，是的话，返回judge(i - 1, j + 1)的值，否则非回文
  4. 返回任意一长度最大的回文子串
0%