网站推广的方法是什么_研发网站建设报价_安卓系统优化app_seo入门培训

1 题目：最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

2 动态规划

这道题第一感觉就是动态规划，用 dp[i][j] 表示区间 [i，j] 是不是回文串，递推公式很简单直接写代码里了。

    string longestPalindrome(string s) {int start = 0, length = 1;bool dp[s.size()][s.size()];dp[0][0] = true;for (int i = 1; i < s.size(); i++) {dp[i][i] = true;dp[i - 1][i] = s[i - 1] == s[i];if (dp[i - 1][i]) start = i-1, length = 2;}for (int len = 3; len <= s.size(); len++) {for (int i = 0; i + len - 1 < s.size(); i++) {int j = i + len - 1;dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1];if (dp[i][j]) start = i, length = len;}}return s.substr(start, length);
}

结果

时间复杂度和空间复杂度均为 $O(N^2)$

3 直接搜索

直接从中间往两边搜索，分为根据奇偶数两种情况。

string longestPalindrome(string s) {int start = 0, length = 1;for(int mid = 0; mid < s.size() ; mid++){int len = 0, sta = 0;for(int i = 1; mid + i < s.size() && mid - i >= 0; i++){// oddif(s[mid + i] == s[mid - i]){sta = mid - i;len = i * 2 + 1;if(len > length){start = sta;length = len;}}elsebreak;}for(int i = 0; mid + i + 1 < s.size() && mid - i >= 0; i++){// evenif(s[mid + i + 1] == s[mid - i]){sta = mid - i;len = i * 2 + 2;if(len > length){start = sta;length = len;}}elsebreak;}}return s.substr(start, length);
}

结果