wordpress 建站简单吗,自我介绍网站html,网站架构拓扑图,做asp.net网站参考文献题目描述
给你一个字符串 s#xff0c;找到 s 中最长的 回文子串。
对于该题使用中心扩展法在某些情况下可以比动态规划方法更优#xff0c;尤其是在处理较长字符串时。这是因为中心扩展法具有更好的空间复杂度#xff0c;并且在实际应用中可能具有更快的运行速度#xf…题目描述
给你一个字符串 s找到 s 中最长的 回文子串。
对于该题使用中心扩展法在某些情况下可以比动态规划方法更优尤其是在处理较长字符串时。这是因为中心扩展法具有更好的空间复杂度并且在实际应用中可能具有更快的运行速度尽管其时间复杂度与动态规划相同均为O(n^2)。但是本专题主要讲解动态规划算法因此不对其过多讲解。
解题思路
当使用动态规划Dynamic Programming, DP方法来解决寻找字符串中最长回文子串的问题时我们主要关注如何定义状态、状态转移方程以及边界条件。下面我将详细讲解这个过程。
1. 定义状态
首先我们需要定义DP数组dp其中dp[i][j]表示字符串s中从索引i到索引j的子串即s[i--j]是否是回文子串。注意这里i和j都是基于0的索引。
2. 初始化状态
对于所有idp[i][i]都是true因为单个字符自然是回文。如果字符串s的长度大于1我们还应该初始化长度为2的子串。即对于所有i如果s[i] s[i1]则dp[i][i1]为true否则为false。
3. 状态转移方程
对于长度大于2的子串s[i--j]如果s[i] s[j]则当s[i--j]是回文的那么s[i1--j-1]也是回文。因此状态转移方程为
dp[i][j] ( s[i] s [j] )∧dp[i1][j−1] .
其中i和j满足j i 1以确保子串s[i1--j-1]的长度至少为1。
4. 边界条件
需要注意i和j的遍历顺序。由于DP表的填充依赖于较小的子问题我们应该从较小的子串开始逐步扩展到较大的子串。这通常意味着外层循环遍历子串的长度从2开始直到整个字符串的长度内层循环遍历起始索引i。当j超出字符串s的边界时应停止内层循环。
5. 记录最长回文子串
在填充DP表的过程中我们可以跟踪并记录遇到的最长回文子串的起始索引和长度。
代码示例
class Solution {
public:string longestPalindrome(string s) {int n s.length();if (n 2)return s; //如果字符串长度小于2直接返回原字符串vectorvectorbool dp(n, vectorbool(n, false));int start 0, maxLength 1; //初始化最长回文子串的起始位置和长度// 初始化长度为1和2的子串for (int i 0; i n; i) {dp[i][i] true; // 单个字符是回文if (i n - 1 s[i] s[i 1]) {dp[i][i 1] true;start i;maxLength 2; //如果找到长度为2的回文子串则更新最长回文子串}}//填充DP表并找到最长回文子串for (int len 3; len n; len) { for (int i 0; i n - len; i) {int j i len - 1;if (s[i] s[j] dp[i 1][j - 1]) {dp[i][j] true;start i; //更新最长回文子串的起始位置maxLength len; //更新最长回文子串的长度}}}//返回最长回文子串return s.substr(start, maxLength);}
}; 中心扩展法
class Solution {
public:string longestPalindrome(string s) {int start 0, maxLength 1;for (int i 0; i s.length(); i) {//奇数长度的回文子串int len1 expandAroundCenter(s, i, i);//偶数长度的回文子串int len2 expandAroundCenter(s, i, i 1);//更新最长回文子串的起始位置和长度int len max(len1, len2);if (len maxLength) {start i - (len - 1) / 2;maxLength len;}}return s.substr(start, maxLength);}int expandAroundCenter(string s, int left, int right) {int L left, R right;while (L 0 R s.length() s[L] s[R]) {L--;R;}//返回以left和right为中心的回文子串的长度注意要1来包含中心字符return R - L - 1;}
};
实现步骤
遍历字符串中的每个字符以及每对相邻字符以处理偶数长度的回文将它们作为潜在的中心点。从中心点开始向两侧扩展检查两侧字符是否相等如果相等则继续扩展直到不再相等为止。在扩展过程中记录遇到的最长回文子串的起始位置和长度。遍历完成后返回最长回文子串。
