Leetcode之5-最长回文子串(Longest Palindromic Substring)

算法题

题干

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

示例

1
2
3
4
5
6
7
8
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:
输入: "cbbd"
输出: "bb"

解法

  1. 暴力解法, 获取字符串的所有子串, 然后遍历所有子串获取最长回文子串。
  2. 动态规划, 可以参考最长回文子串动态规划
  3. 中心扩展方法。回文子串从中间节点(解释下中间节点: 偶数个节点即中间两个, 奇数个节点即中间那个节点)往两边扩散, 以中间节点为中心点回文子串肯定为对称结构。我们可以依据这个特点去循环遍历原始字符串, 依次以字符串每个字符(可能包含后面一个字符)为中心节点, 往外扩散直到找到对称字符不相同为止。

解法3 Java代码

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
public String longestPalindrome(String s) {
if (s == null) {
return "";
}
final int LEN = s.length();
if (LEN <= 1) {
return s;
}
String temp = "";
for (int i = 0; i < LEN; i++) {
String data = findPalindrome(s, i, i);
if (data.length() > temp.length()) {
temp = data;
}
data = findPalindrome(s, i, i+1);
if (data.length() > temp.length()) {
temp = data;
}
}
return temp;
}

private String findPalindrome(String s, int left, int right) {
final int LEN = s.length();
while (left >= 0 && right < LEN && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return s.substring(left+1, right);
}

代码解析

  1. 第11行代码表示找以每个字符为中心节点的回文子串。
  2. 第15行代码表示找以每个字符及其后一字符为中心节点的回文子串。
  3. 第22-30行代码表示找以left和right为中心节点的回文子串。
如果有任何错误或疑问, 欢迎小伙伴们评论区留言^-^
( 完 )

欢迎各位看官关注

麻辣烫,走起
0%