Keshawn_lu's Blog

Leetcode 5. 最长回文子串

字数统计: 392阅读时长: 1 min
2020/05/21 Share

题目简介:

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

示例 1:

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

示例 2:

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

思路:

定义一个dp[i][j]数组,来判断s[i]……s[j]的子字符串是否为回文串。

遍历字符串,若s[i] == s[j],则存在以下两种情况都可判别s[i]……s[j]为回文串:

  1. dp[i + 1][j - 1] == true
  2. j - i <= 2,这种情况说明ij之间最多存在一个字符,若s[i] == s[j],则s[i]……s[j]自然为回文串了

然后每次保存最长的子回文串,最后返回即可。

tip:

  • 遍历时,需要以字符串结尾为开始(即结尾为最外层的循环,字符串开始的位置从0依次增加到结尾的位置),这样子才能保证判断dp[i + 1][j - 1]时不出错。
  • 需要注意substr()的使用方法。

代码如下:

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
class Solution {
public:
string longestPalindrome(string s) {

//判断[i……j]是否为回文串
vector<vector<bool>> dp(s.length(), vector<bool>(s.length()));

if(s.size() == 0)
return "";

int max_length = 0;
string res = "";
res += s[0];


for(int j = 1; j < s.length(); j++){

for(int i = 0; i <= j; i++){

if(s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1])){

dp[i][j] = true;

if(j - i + 1 > max_length){

max_length = j - i + 1;
res = s.substr(i, j - i + 1);
}
}
}
}

return res;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: