题目描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
动态规划法
算法设计
- 构造一个长宽等于字符串长度的二维数组dp[len][len]，其中len = str.length()；
- 若原字符串中从第i个字符（从0开始计）到第j个字符之间的子串是符合题目要求的回文子串，则用dp[i][j]表示其长度，若不是回文子串，则记为0
dp[i][j]应该满足如下递归式：
- 最后通过max，left定位子串
代码实现
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
| private static String findSubstring(String str) {
if (str == null || str.length() == 0) return str;
int[][] dp = new int[str.length()][str.length()];
int len = dp.length;
int max = 1;
int left = 0;
for (int i = 0; i < len; i++) {
dp[i][i] = 1;
}
for (int j = 1; j < len; j++) {
for (int i = j - 1; i >= 0; i--) {
if (str.charAt(i) == str.charAt(j)) {
if (j - i == 1) {
dp[i][j] = 2;
} else {
dp[i][j] = (dp[i + 1][j - 1] > 0)? dp[i + 1][j - 1] + 2 : 0;
}
} else {
dp[i][j] = 0;
}
if (dp[i][j] > max) {
max = dp[i][j];
left = i;
}
}
}
return str.substring(left, max + left);
}
|
前向与后向相等子串
题目描述
设计一个动态规划算法，找到字符串T[1..n]中前向和后向相同的最长连续子串。前向子串和后项子串不能重叠。例如：
输入“ALGORITHM”，算法返回空串；
输入“RCURSION”，算法返回“R”；
输入“REDIVIDE”，算法返回“EDI”。
算法设计
构造一个长宽等于字符串长度的二维数组dp[len][len]，其中len = str.length()；
dp[i][j]表示原字符串中从第i个字符（从0开始计）到第j个字符之间符合题目要求的最大长度，由于题目要求不重叠，可将dp[i][i]的值设置为0；
dp[i][j]应该满足如下递归式：
设置max = 0，left表示包含前向子串和后向子串的最小左边界，比如在“REIE”中，max = 3，left = 1。当str[i]和str[j]相等时，在获得dp[i][j]的值后，令max = dp[i][j]，left = i，最终通过这两个参数定位子串
代码实现
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
| private static String findSubstring(String str) {
int[][] dp = new int[str.length()][str.length()];
int len = dp.length;
int max = 0;
int left = 0;
for (int i = 0; i < len; i++) {
dp[i][i] = 0;
}
for (int j = 1; j < len; j++) {
for (int i = j - 1; i >= 0; i--) {
if (str.charAt(i) == str.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 1;
if (dp[i][j] > max) {
max = dp[i][j];
left = i;
}
} else {
dp[i][j] = (dp[i][j - 1] > dp[i + 1][j]) ? dp[i][j - 1] : dp[i + 1][j];
}
}
}
return str.substring(left, max + left);
}
|