想法: 当一个字符串是回文的时候,在它的首尾加上同样的字母时 加上之后的字符串依旧是一个回文字符串。
string longestPalindrome(string s) {
//初始化
if (s.empty()) return "";
if (s.size() == 1) return s;
int min_start = 0, max_len = 1;
for (int i = 0; i < s.size();) {
// 因为i 标记的可能是中间点的位置 所以当i所在的位置之后剩余字母 比当前最大回文串字符的一半还要小时
// 就算后面还存在一个回文子串也不可能是最大的了 直接break
if (s.size() - i <= max_len / 2) break;
int j = i, k = i;
while (k < s.size() - 1 && s[k + 1] == s[k])
// 跳过重复的字符 重复字符一定是回文
// j 指向重复字符前 遍历完之后K指向重复位置之后
++k;
i = k + 1;
// i 标记可能是中间点的位置
//不能交换顺序 因为任何点都可能是新的中间点
while (k < s.size() - 1 && j > 0 && s[k + 1] == s[j - 1]) {
// 找到中间点 往两边拓展
++k;
--j;
}
// 贪心 选择Max
int new_len = k - j + 1;
if (new_len > max_len) {
min_start = j;
max_len = new_len;
}
}
return s.substr(min_start, max_len);
}
网友评论