原題鏈接： 最長回文字符串

給你一個字符串 s，找到 s 中最長的回文子串。

示例 1：

輸入：s = “babad”
輸出：“bab”
解釋：“aba” 同樣是符合題意的答案。
示例 2：

輸入：s = “cbbd”
輸出：“bb”
示例 3：

輸入：s = “a”
輸出：“a”
示例 4：

輸入：s = “ac”
輸出：“a”

提示：

1 <= s.length <= 1000
s 僅由數字和英文字母（大寫和/或小寫）組成

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

暴力求解中心擴散思想和運籌學中的狀態轉移實現；

只有對應線上全為TRUE的時候才能保證當前字符子串是回文子串，詳解間官方視頻教程

官方求最長回文子串詳解

語言實現：

package mainimport "fmt"// 官方解答 使用運籌學中的遞歸 func longestPalindrome2(s string) string {n := len(s)ans := ""dp := make([][]int, n)for i := 0; i < n; i++ {dp[i] = make([]int, n)}for l := 0; l < n; l++ {for i := 0; i + l < n; i++ {j := i + lif l == 0 {dp[i][j] = 1} else if l == 1 {if s[i] == s[j] {dp[i][j] = 1}} else {if s[i] == s[j] {dp[i][j] = dp[i+1][j-1]}}if dp[i][j] > 0 && l + 1 > len(ans) {ans = s[i:i+l+1]}}}return ans }// 官方解答2 暴力解答 func longestPalindrome(s string) string {if s == "" {return ""}start, end := 0, 0for i := 0; i < len(s); i++ {left1, right1 := expandAroundCenter(s, i, i)left2, right2 := expandAroundCenter(s, i, i + 1)if right1 - left1 > end - start {start, end = left1, right1}if right2 - left2 > end - start {start, end = left2, right2}}// 字符串截取return s[start:end+1] }func expandAroundCenter(s string, left, right int) (int, int) {for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1 , right+1 { }return left + 1, right - 1 }func main() {fmt.Println(longestPalindrome("abababhjjh")) }

CPP代碼實現：

// // Created by andrew on 2021/3/7. // #include <iostream> #include <string> #include <vector>using namespace std;class Solution { public: // 官方使用動態規劃static string longestPalindrome(string s) {int n = s.size();vector<vector<int>> dp(n, vector<int>(n));string ans;for (int l = 0; l < n; ++l) {for (int i = 0; i + l < n; ++i) {int j = i + l;if (l == 0) {dp[i][j] = 1;} else if (l == 1) {dp[i][j] = (s[i] == s[j]);} else {dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);}cout <<"i = " << i << " j = " << j << " l = " << l << endl;if (dp[i][j] && l + 1 > ans.size()) {ans = s.substr(i, l + 1);}}cout << "======================" << endl;}return ans;}static pair<int, int> expandAroundCenter(const string& s, int left, int right) {while (left >= 0 && right < s.size() && s[left] == s[right]) {--left;++right;}return {left + 1, right - 1};}// 暴力破解static string longestPalindrome2(string s) {int start = 0, end = 0;pair<int, int> point1, point2;for (int i =0; i < s.size(); i ++) {// aba 型point1 = expandAroundCenter(s, i, i);// abba 型point2 = expandAroundCenter(s, i, i + 1);if(point1.second - point1.first > end - start) {start = point1.first;end = point1.second;}if (point2.second - point2.first > end - start) {start = point2.first;end = point2.second;}}return s.substr(start, end - start + 1);}};int main(int argc, char*argv[]) {cout << Solution::longestPalindrome("abba") << endl;cout << Solution::longestPalindrome2("abba") << endl;return 0; }

總結

以上是生活随笔為你收集整理的leetCode第五题-求字符串最长回文字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。