Catalog
  1. 1. 5. Longest Palindromic Substring
LeetCode Solution: 5. Longest Palindromic Substring

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Example 2:

Input: “cbbd”
Output: “bb”

解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
std::string longestPalindrome(std::string s)
{
std::string res;
int size = s.size();
std::vector<std::vector<int>> P(size, std::vector<int>(size));

for (int i = 0; i < size; ++i)
P[i][i] = 1;
for (int i = 0; i < size - 1; ++i)
P[i][i + 1] = (s[i] == s[i + 1]);

for (int i = size - 1; i >= 0; --i)
for (int j = size - 1; j >= i; --j) {
if (i + 1 <= j - 1)
P[i][j] = (P[i + 1][j - 1] && s[i] == s[j]);
if (P[i][j] && res.size() < (j - i + 1))
res = s.substr(i, j - i + 1);
}
return res;
}
};

题目求一个字符串中的最长回文串,可以用动态规划的思想。

考虑情况“ababa“,如果我们知道bab是一个回文串,显而易见ababa也是一个回文串,因为它两头的字母是相同的。

首先我们定义一个
$$
P(i, j)
\left\{
\begin{array}{lr}
true, \quad S_i…S_j是回文串\\\\
false, \quad S_i…S_j不是回文串
\end{array}
\right.
$$

因此,
$$
P(i,j) = (P(i+1,j-1);and;S_i == S_j)
$$
并且数组初始化时候为:

  1. $P(i,i) = true$
  2. $P(i,i+1) = (S_i==S_{i+1})$

算法

  1. 第一遍循环,把数组中所有一个字母的都认为是回文串
  2. 第二遍循环,把相邻位置相同字母的认为是回文串
  3. 对整个数组从后往前遍历,当遇到中间为回文串,两边相同的时候把它设为回文串
  4. 如果此时判断的字符串是回文串,且res的长度小于当前判断的字符串长度,就把当前字符串当做res

Complexity Analysis

  • Time complexity : O(n^2)O(n2). This gives us a runtime complexity of O(n^2)O(n2).
  • Space complexity : O(n^2)O(n2). It uses O(n^2)O(n2) space to store the table.
Author: Jsthcit
Link: http://jsthcitpizifly.com/2020/07/29/LeetCode-Solution-5/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶