我是小张同学，立志用最简洁的代码做最高效的表达
以下是我个人做的题解，每个题都尽量囊括了所有解法，并做到了最优解，欢迎大家收藏！留言！
| 题解 | 分类 |
|---|---|
| Leecode01. 两数之和（C++） | hash |
| Leecode02. 两数相加（C++） | 链表 |
| Leecode03. 无重复字符的最长子串（C++） | hash + 滑动窗口 |
问题描述
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：
输入：s = “cbbd”
输出：“bb”示例 3：
输入：s = “a”
输出：“a”
示例 4：
输入：s = “ac”
输出：“a”
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
思路
中心探测法（解回文串常用的方法）
复杂度分析
时间复杂度： O ( n 2 ) O(n^2) O(n2)，其中 n n n 是字符串的长度。长度为 1 1 1 和 2 2 2 的回文中心分别有 n n n 和 n − 1 n-1 n−1 个，每个回文中心最多会向外扩展 O ( n ) O(n) O(n) 次。
空间复杂度： O ( 1 ) O(1) 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++) {
// 回文数列为奇数
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);
}
// 回文数列为偶数
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：函数复用
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++) {
// 回文数列为奇数
nowLen = 1;
sta = func(nowLen, i-1, i+1, s);
if(nowLen > maxLen) {
maxLen = nowLen;
res = s.substr(sta+1, maxLen);
}
// 回文数列为偶数
nowLen = 0;
sta = func(nowLen, i, i+1, s);
if(nowLen > maxLen) {
maxLen = nowLen;
res = s.substr(sta+1, maxLen);
}
}
return res;
}
};