leetcode 5st Longest Palindromic Substring
程序员文章站
2024-02-01 21:33:58
...
1.题意
寻找输入字符串中的最长回文序列
2.思路比较
(1)暴力**,从头开始首尾两下标向中间移动,比较两端字符是否相同,长度控制一层循环,字符串起始位控制一层循环,比较两端字符是否相同一层循环,时间复杂度为O(n^3)代码不ac
(2)以每个字符为中心向两边扩散比较,去除长度控制这层循环,与两端标记一同控制,
时间复杂度为O(n^2)
参考代码如下:
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() <= 1) return s;
int startIdx = 0, left = 0, right = 0, len = 0;
for (int i = 0; i < s.size() - 1; ++i) {
if (s[i] == s[i + 1]) {
left = i;
right = i + 1;
searchPalindrome(s, left, right, startIdx, len);
}
left = right = i;
searchPalindrome(s, left, right, startIdx, len);
}
return s.substr(startIdx, len);
}
void searchPalindrome(string s, int left, int right, int &startIdx, int &len) {
int step = 1;
while ((left - step) >= 0 && (right + step) < s.size()) {
if (s[left - step] != s[right + step]) break;
++step;
}
int wide = right - left + 2 * step - 1;
if (len < wide) {
len = wide;
startIdx = left - step + 1;
}
}
};
在处理奇偶回文序列的时候,这里使用的条件很精巧
//偶数回文序列,中间两个字符相等
if (s[i] == s[i + 1])
//否则,直接取正中心的字符,向两侧移动
left = right = i;
另外在view code的时候,有这么一段琢磨了一会
int wide = right - left + 2 * step - 1;
式子中的-1一直很困惑,后面才发觉与初始的step=1有关,已经预先往两侧移动一步
原公式应为
int wide = right - left -1+ 2 * step + 2;
(3)动态规划算法
将已经比较好是否为回文序列的结果储存在二维数组中,减少重复比较
动态规划算法适用的情况,1最优化子结构 2无后效性 3子问题的重叠,具体学习会在另一篇博文中呈现
关键,找到状态转移方程,这里就有点像数学归纳法,两端字符相同,若子结构为真,则该结构为真
dp[i, j] = 1 if i == j
= s[i] == s[j] if j = i + 1
= s[i] == s[j] && dp[i + 1][j - 1] if j > i + 1
代码
// DP
class Solution {
public:
string longestPalindrome(string s) {
int dp[s.size()][s.size()] = {0}, left = 0, right = 0, len = 0;
for (int i = 0; i < s.size(); ++i) {
for (int j = 0; j < i; ++j) {
dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1]));
if (dp[j][i] && len < i - j + 1) {
len = i - j + 1;
left = j;
right = i;
}
}
dp[i][i] = 1;
}
return s.substr(left, right - left + 1);
}
};
动态规划的矩阵,赋值时,j-i<2涵盖了两种情况 j=i, j-1=1。
状态转移方程在代码中的体现,精妙。
dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1]));
reference:ref
上一篇: 练习2-14 求奇数分之一序列前N项和 (15分)
下一篇: 习题2-2 阶梯电价 (15分)
推荐阅读
-
leetcode 5st Longest Palindromic Substring
-
Leetcode Two Sum (java)Longest Substring Without Repeating Characters
-
LeetCode - 3.Longest Substring Without Repeating Characters(388ms)
-
[LeetCode]3.Longest Substring Without Repeating Characters
-
Leetcode_3. Find the longest substring without repeating characters
-
3-Longest Substring Without Repeating Characters @LeetCode
-
LeetCode-5. Longest Palindromic Substring(三种解法及Manacher算法详解)
-
Longest Substring Without Repeating Characters (leetcode 3)
-
【Leetcode 3】Longest Substring Without Repeating Characters
-
Leetcode 3 Longest Substring Without Repeating Characters