我是小張同學(xué)，立志用最簡(jiǎn)潔的代碼做最高效的表達(dá)

---

以下是我個(gè)人做的題解，每個(gè)題都盡量囊括了所有解法，并做到了最優(yōu)解，歡迎大家收藏！留言！

傳送門——>Leecode大廠熱題100道系列題解

---

問(wèn)題描述

給你一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。

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

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

示例 3：

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

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

提示：
1 <= s.length <= 1000
s 僅由數(shù)字和英文字母（大寫(xiě)和/或小寫(xiě)）組成

---

思路

中心探測(cè)法（解回文串常用的方法）

---

復(fù)雜度分析

時(shí)間復(fù)雜度：$O(n^2)$，其中 $n$ 是字符串的長(zhǎng)度。長(zhǎng)度為 $1$ 和 $2$ 的回文中心分別有 $n$ 和 $n?1$ 個(gè)，每個(gè)回文中心最多會(huì)向外擴(kuò)展 $O(n)$ 次。

空間復(fù)雜度：$O(1)$。

---

代碼一（普適性代碼）

class Solution { public:string longestPalindrome(string s) {int left = 0, right = s.length() - 1;int maxLen = 0, nowLen = 0;string res = "";for(int i = 0; i < s.length(); i++) {// 回文數(shù)列為奇數(shù)nowLen = 1;int l = i-1, r = i+1;while (l >= left && r <= right) {if(s[l] == s[r]) {nowLen += 2;} else {break;}l--; r++;}if(nowLen > maxLen) {maxLen = nowLen;res = s.substr(l+1, maxLen);}// 回文數(shù)列為偶數(shù)nowLen = 0;l = i, r = i+1;while (l >= left && r <= right) {if(s[l] == s[r]) {nowLen += 2;} else {break;}l--; r++;}if(nowLen > maxLen) {maxLen = nowLen;res = s.substr(l+1, maxLen);}}return res;} };

---

代碼2：函數(shù)復(fù)用

class Solution { public:int func(int& nowLen, int l, int r, string s) {while (l >= 0 && r <= s.length()) {if(s[l] == s[r]) {nowLen += 2;} else {break;}l--; r++;}return l;}string longestPalindrome(string s) {int maxLen = 0, nowLen, sta;string res = "";for(int i = 0; i < s.length(); i++) {// 回文數(shù)列為奇數(shù)nowLen = 1;sta = func(nowLen, i-1, i+1, s);if(nowLen > maxLen) {maxLen = nowLen;res = s.substr(sta+1, maxLen);}// 回文數(shù)列為偶數(shù)nowLen = 0;sta = func(nowLen, i, i+1, s);if(nowLen > maxLen) {maxLen = nowLen;res = s.substr(sta+1, maxLen);}}return res;} };

---

當(dāng)你覺(jué)得自己很聰明，所有人都開(kāi)始夸贊你的時(shí)候，其實(shí)你只是在收割你以前的積累而已。

總結(jié)

以上是生活随笔為你收集整理的Leecode05. 最长回文子串——Leecode大厂热题100道系列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。