1第 5 题常用的是：
2
3中心扩展双指针
4
5也就是：从某个中心开始，left 向左走，right 向右走。所以它不是“相向双指针”，而是中心扩展
62. 前提条件
7
8第 5 题要找：最长回文子串
9
10回文串就是：正着读和反着读一样。
11
12例如：
13
14"aba"
15"abba"
16"bb"
17
18都是回文。
19
20不是回文：
21
22"abc"
23"abca"
24
253. 核心概念：回文有中心
26每一个回文串都有中心。
27
28但是中心有两种情况。
29
30情况一：奇数长度回文
31
32例如："aba"
33
34中心是：'b'
35
36形式：
37
38left = i
39right = i
40情况二：偶数长度回文
41
42例如：
43
44"abba"
45
46中心在两个字符中间：
47
48'b' 和 'b' 中间
49
50形式：
51
52left = i
53right = i + 1
54
55所以每个位置都要尝试两种中心：
56
571. 以 i 为中心
582. 以 i 和 i+1 中间为中心
594. 中心扩展模板
60while (left >= 0 && right < n && s[left] == s[right]) {
61 left--;
62 right++;
63}
64
65循环结束时，说明越界了，或者左右字符不相等了。
66此时left已经减去了1和right已经加上了1，所以回调回去就行
67此时真正的回文范围是：
68
69[left + 1, right - 1]
70right-1-(left+1)+1=right-lift-1
71长度是：right - left - 1
72因为循环最后一次失败时，left 和 right 已经多走了一步。
73
745. 第 5 题 C 语言题解
75
76LeetCode 第 5 题返回 char*，所以需要 malloc 一个答案字符串。
77
78#include <stdlib.h>
79#include <string.h>
80
81int expand(char* s, int n, int left, int right) {
82 while (left >= 0 && right < n && s[left] == s[right]) {
83 left--;
84 right++;
85 }
86//这里就是从0开始往右边遍历寻找那个回文中心
87 return right - left - 1;
88}
89
90char* longestPalindrome(char* s) {
91 int n = strlen(s);
92
93 int start = 0;
94 int maxLen = 1;
95
96 for (int i = 0; i < n; i++) {
97 int len1 = expand(s, n, i, i);
98 int len2 = expand(s, n, i, i + 1);
99//len1是奇中心的算法，len2是偶中心的算法
100 int len;
101 if (len1 > len2) {
102 len = len1;
103 } else {
104 len = len2;
105 }
106
107 if (len > maxLen) {
108 maxLen = len;
109 start = i - (len - 1) / 2;
110 }
111 }
112//之后两者比较算出最大的len之后，计算起始start位置
113 char* ans = malloc((maxLen + 1) * sizeof(char));
114
115 for (int i = 0; i < maxLen; i++) {
116 ans[i] = s[start + i];
117 }
118
119 ans[maxLen] = '\0';
120
121 return ans;
122}
1236. start = i - (len - 1) / 2 怎么来的？
124
125这个公式用来根据中心 i 和回文长度 len 求起点。
126
127奇数回文时
128例如：
129
130s = "babad"
131中心 i = 1，对应 'a'
132回文 = "bab"
133len = 3
134
135起点：
136i - (len - 1) / 2
137= 1 - (3 - 1) / 2
138= 1 - 1
139= 0
140
141所以从 0 开始。
142
143偶数回文时
144例如：
145
146s = "cbbd"
147中心 i = 1 和 i+1 = 2
148回文 = "bb"
149len = 2
150
151起点：
152
153i - (len - 1) / 2
154= 1 - (2 - 1) / 2
155= 1 - 0
156= 1
157
158所以从 1 开始。
159
160这个公式同时适用于奇数和偶数。
161
1627. 第 5 题易错点
163易错点 1：只考虑奇数回文
164
165如果只写：expand(s, n, i, i);
166
167就会漏掉：
168
169"bb"
170"abba"
171
172所以必须还要写：expand(s, n, i, i + 1);
173
174易错点 2：循环结束后范围多走了一步
175
176中心扩展结束时：
177left 和 right 已经不属于回文范围。
178
179真正范围是：
180
181left + 1 到 right - 1
182
183长度是：
184
185right - left - 1
186易错点 3：返回字符串要补 '\0'
187常识需要知道
188C 语言字符串必须以 '\0' 结尾。
189
190所以：
191
192ans[maxLen] = '\0';
193
194
1958. 第 5 题复杂度
196
197中心扩展法：
198
199时间复杂度：O(n^2)
200空间复杂度：O(1)
201
202如果算返回字符串空间，就是：O(n)
203
2049. 题型总结
205第 5 题可以用双指针，但不是普通相向双指针。
206
207普通相向双指针：
208 left 从头开始
209 right 从尾开始
210 两边往中间走
211
212最长回文子串：
213 从中心开始
214 left 向左走
215 right 向右走
216 两边向外扩展
217
218第 5 题的双指针是“中心扩展”，核心是枚举中心，然后向两边扩展。
第 5 题常用的是：
中心扩展双指针
也就是：从某个中心开始，left 向左走，right 向右走。所以它不是“相向双指针”，而是中心扩展
2. 前提条件
第 5 题要找：最长回文子串
回文串就是：正着读和反着读一样。
例如：
"aba"
"abba"
"bb"
都是回文。
不是回文：
"abc"
"abca"
- 核心概念：回文有中心
每一个回文串都有中心。
但是中心有两种情况。
情况一：奇数长度回文
例如："aba"
中心是：'b'
形式：
left = i
right = i
情况二：偶数长度回文
例如：
"abba"
中心在两个字符中间：
'b' 和 'b' 中间
形式：
left = i
right = i + 1
所以每个位置都要尝试两种中心：
- 以 i 为中心
- 以 i 和 i+1 中间为中心
- 中心扩展模板
while (left >= 0 && right < n && s[left] == s[right]) {
left--;
right++;
}
循环结束时，说明越界了，或者左右字符不相等了。
此时left已经减去了1和right已经加上了1，所以回调回去就行
此时真正的回文范围是：
[left + 1, right - 1]
right-1-(left+1)+1=right-lift-1
长度是：right - left - 1
因为循环最后一次失败时，left 和 right 已经多走了一步。
- 第 5 题 C 语言题解
LeetCode 第 5 题返回 char*，所以需要 malloc 一个答案字符串。
#include <stdlib.h>
#include <string.h>
int expand(char* s, int n, int left, int right) {
while (left >= 0 && right < n && s[left] == s[right]) {
left--;
right++;
}
//这里就是从0开始往右边遍历寻找那个回文中心
return right - left - 1;
}
char* longestPalindrome(char* s) {
int n = strlen(s);
int start = 0;
int maxLen = 1;
for (int i = 0; i < n; i++) {
int len1 = expand(s, n, i, i);
int len2 = expand(s, n, i, i + 1);
//len1是奇中心的算法，len2是偶中心的算法
int len;
if (len1 > len2) {
len = len1;
} else {
len = len2;
}
if (len > maxLen) {
maxLen = len;
start = i - (len - 1) / 2;
}
}
//之后两者比较算出最大的len之后，计算起始start位置
char* ans = malloc((maxLen + 1) * sizeof(char));
for (int i = 0; i < maxLen; i++) {
ans[i] = s[start + i];
}
ans[maxLen] = '\0';
return ans;
}
6. start = i - (len - 1) / 2 怎么来的？
这个公式用来根据中心 i 和回文长度 len 求起点。
奇数回文时
例如：
s = "babad"
中心 i = 1，对应 'a'
回文 = "bab"
len = 3
起点：
i - (len - 1) / 2
= 1 - (3 - 1) / 2
= 1 - 1
= 0
所以从 0 开始。
偶数回文时
例如：
s = "cbbd"
中心 i = 1 和 i+1 = 2
回文 = "bb"
len = 2
起点：
i - (len - 1) / 2
= 1 - (2 - 1) / 2
= 1 - 0
= 1
所以从 1 开始。
这个公式同时适用于奇数和偶数。
- 第 5 题易错点
易错点 1：只考虑奇数回文
如果只写：expand(s, n, i, i);
就会漏掉：
"bb"
"abba"
所以必须还要写：expand(s, n, i, i + 1);
易错点 2：循环结束后范围多走了一步
中心扩展结束时：
left 和 right 已经不属于回文范围。
真正范围是：
left + 1 到 right - 1
长度是：
right - left - 1
易错点 3：返回字符串要补 '\0'
常识需要知道
C 语言字符串必须以 '\0' 结尾。
所以：
ans[maxLen] = '\0';
- 第 5 题复杂度
中心扩展法：
时间复杂度：O(n^2)
空间复杂度：O(1)
如果算返回字符串空间，就是：O(n)
- 题型总结
第 5 题可以用双指针，但不是普通相向双指针。
普通相向双指针：
left 从头开始
right 从尾开始
两边往中间走
最长回文子串：
从中心开始
left 向左走
right 向右走
两边向外扩展
第 5 题的双指针是“中心扩展”，核心是枚举中心，然后向两边扩展。
