5_最长回文子串
【问题描述】
给你一个字符串 s
,找到 s
中最长的回文子串。
示例:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
【算法设计思想】
本题主要使用到了动态规划的算法思想。其程序的大致执行过程如下:
首先,我们先求取下该字符串的长度,然后判断下这个字符串的长度是否为0或者1,如果是0或者1,则直接返回即可。如果不是,则我们让子串的长度从2开始,我们逐个遍历字符串即可。
在此,我们先默认设计下几个参数:
maxLen,即最长回文子串的长度。
begin,即最长回文子串的左索引。
dp,即用来记录存储结果一个二维数组。每个单独的字符串我们都可以看作是一个回文子串,故我们初始化其对角线上的元素为true。
接下来正式进入本算法的核心过程,先从L=2开始逐个遍历,然后在循环内部,i代表左索引,j代表右索引,然后判断下s[i]和s[j]是否相等,如果不相等则说明是一个长度为2的回文子串,设置为false;如果不相等,则再判断下j - i(即子串的长度L)是否小于3,如果小于3则设置dp为true,如果大于3,则利用到对应的状态转移方程,我们判断其子串即可。
最后判断更新下maxLen和begin的值,返回子串。
【算法描述】
C++:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
vector<vector<int>> dp(n, vector<int>(n));
// 初始化:所有长度为 1 的子串都是回文串
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= n; L++) {
// 枚举左边界,左边界的上限设置可以宽松一些
for (int i = 0; i < n; i++) {
// 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界,就可以退出当前循环
if (j >= n) {
break;
}
if (s[i] != s[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substr(begin, maxLen);
}
};
Java:
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
boolean[][] dp = new boolean[len][len];
// 初始化:所有长度为 1 的子串都是回文串
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= len; L++) {
// 枚举左边界,左边界的上限设置可以宽松一些
for (int i = 0; i < len; i++) {
// 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界,就可以退出当前循环
if (j >= len) {
break;
}
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
Python:
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n < 2:
return s
max_len = 1
begin = 0
# dp[i][j] 表示 s[i..j] 是否是回文串
dp = [[False] * n for _ in range(n)]
for i in range(n):
dp[i][i] = True
# 递推开始
# 先枚举子串长度
for L in range(2, n + 1):
# 枚举左边界,左边界的上限设置可以宽松一些
for i in range(n):
# 由 L 和 i 可以确定右边界,即 j - i + 1 = L 得
j = L + i - 1
# 如果右边界越界,就可以退出当前循环
if j >= n:
break
if s[i] != s[j]:
dp[i][j] = False
else:
if j - i < 3:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
# 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置
if dp[i][j] and j - i + 1 > max_len:
max_len = j - i + 1
begin = i
return s[begin:begin + max_len]
标签:子串,begin,len,maxLen,最长,dp,回文
From: https://www.cnblogs.com/zeta186012/p/18389090