-
Notifications
You must be signed in to change notification settings - Fork 13
/
Copy pathSolution0005.java
129 lines (119 loc) · 4.66 KB
/
Solution0005.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
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// 5. 最长回文子串
/*
暴力破解:列举所有的子串,判断是否为回文串,保存最长的回文串
*/
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 0;
String res = "";
for (int l = 0; l < len; l++) {
for (int r = l + maxLen; r <= len; r++) {
String sub = s.substring(l, r);
int subLen = sub.length();
if (isPalindrome(sub) && subLen > maxLen) {
res = sub;
maxLen = subLen;
}
}
}
return res;
}
private boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
if (s.charAt(l) != s.charAt(r)) {
return false;
}
l++;
r--;
}
return true;
}
// 方法同上,使用for替代while
private boolean isPalindrome(String s) {
for (int l = 0, r = s.length() - 1; l < r; l++, r--) {
if (s.charAt(l) != s.charAt(r)) {
return false;
}
}
return true;
}
}
/*
中心扩散:
1、遍历字符,以当前字符为中心向两边扩散,包括奇数和偶数回文串两种中心,得到当前中心的回文串长度
2、比较并记录所有中心的最长回文串长度和对应起点,最后截取并返回最长回文子串
*/
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int start = 0;
for (int i = 0; i < len - 1; i++) {
int oddLen = expandAroudCenter(s, i, i);
int evenLen = expandAroudCenter(s, i, i + 1);
int curMaxLen = Math.max(oddLen, evenLen);
if (curMaxLen > maxLen) {
maxLen = curMaxLen;
start = i - (maxLen - 1) / 2;
}
}
return s.substring(start, start + maxLen);
}
private int expandAroudCenter(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
return r - l - 1;
}
}
/*
与“647.回文子串”相似
动态规划:动态规划是暴力破解的优化,两者同样需要遍历列举判断所有子串是否为回文串,区别是暴力破解每次都要对子串单独处理判断是否为回文串,动态规划可以利用之前记录的子串结果直接判断当前子串是否为回文串
1、题目:给你一个字符串 s,找到 s 中最长的回文子串。
2、题目简化:求字符串s的最长回文子串。要先判断子串是否为回文串,再从回文子串中取最长。
3、定义dp数组:dp[l][r]表示子串s[l,r]是否为回文子串,l是左区间,r是右区间
4、初始化:
1)二维dp数组不用扩容,直接根据dp数组的定义就可以直观地对应进行初始化
2)boolean数组创建时,默认值是false,只需要标记为true的地方即可。可以初始化dp数组 dp[i][i] = true,表示1个字符是回文
5、状态转移方程:dp[l][r] = (s[l] == s[r]) and (r - l < 3 or dp[l + 1][r - 1])
1)s[l] == s[r] 表示首尾两个字符相等
2)r - l < 3 表示去掉首尾后剩余0或1个字符时仍是回文。作用包含了1个字符是回文,所以不用初始化dp数组单个字符为true
3)dp[l + 1][r - 1] 表示去掉首尾后的区间是否回文
6、遍历dp数组填表:一个for遍历子串的右区间,另一个for循环遍历子串的左区间,根据状态转移方程推断计算未知结果并填表,当是回文串时比较并记录最长长度和左右区间位置
7、返回结果:根据遍历时记录的最长回文子串左右区间位置,截取字符串s得到最长回文子串
s: b a b a d
↑ ↑
l r
*/
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) {
return s;
}
int maxLen = 1, start = 0, end = 0;
boolean[][] dp = new boolean[n][n];
for (int r = 1; r < n; r++) {
for (int l = 0; l < r; l++) {
if (s.charAt(l) == s.charAt(r) && (r - l < 3 || dp[l + 1][r - 1])) {
dp[l][r] = true;
if (r - l + 1 > maxLen) {
maxLen = r - l + 1;
start = l;
end = r;
}
}
}
}
return s.substring(start, end + 1);
}
}