字符串算法题，本质上就是“数组操作”加上“字符编码转换”以及“人类手工计算过程的代码化”。
例题剖析
题目一：最长公共前缀
解法一：
class Solution { public: string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; string ret = strs[0]; for (int i = 1; i < strs.size(); i++) { ret = findCommon(ret, strs[i]); } return ret; } string findCommon(string& s1, string& s2) { int i = 0; while (i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++; return s1.substr(0, i); } };代码逻辑解析
这段代码采用了逐个比较的思想：
初始化：
string ret = strs[0];
将结果字符串ret初始化为字符串数组中的第一个字符串。这是一个常见的策略，把第一个字符串当作“基准”。遍历数组：
for (int i = 1; i < strs.size(); i++)
从第二个字符串开始，依次遍历数组中的每一个字符串。寻找公共部分：
ret = findCommon(ret, strs[i]);
对于每一个遍历到的字符串strs[i]，调用findCommon函数来求它与当前ret的最长公共前缀，并将结果更新回ret。这意味着ret的长度会随着遍历过程不断缩短，最终保留下来的就是所有字符串的公共前缀。辅助函数
findCommon：使用
while循环，条件是两个字符串都没有越界（i < min(s1.size(), s2.size())）且当前字符相同（s1[i] == s2[i]）。循环结束时，
i的值就是公共前缀的长度。最后通过
s1.substr(0, i)截取并返回公共前缀。
复杂度分析
时间复杂度：O(N×M)。其中 N 是字符串数组的长度，M 是字符串的平均长度。最坏情况下，需要比较所有字符串的每一个字符。
空间复杂度：O(1)（不考虑返回值占用的空间）。代码只使用了常数级别的额外变量
i。
解法二：
class Solution { public: string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; for (int i = 0; i < strs[0].size(); i++) { char tmp = strs[0][i]; for (int j = 1; j < strs.size(); j++) { if (i == strs[j].size() || tmp != strs[j][i]) return strs[0].substr(0, i); } } return strs[0]; } };代码逻辑解析
这段代码的核心思想是：同时比较所有字符串的同一列（同一个索引位置）。
外层循环（列遍历）：
for(int i = 0; i < strs[0].size(); i++)
以第一个字符串strs[0]作为基准。循环变量i代表当前正在比较的字符索引（列）。因为公共前缀不可能比第一个字符串还长，所以以它的长度作为循环上限。取基准字符：
char tmp = strs[0][i];
取出第一个字符串在第i个位置的字符，作为这一列的对比基准。内层循环（行遍历）：
for(int j = 1; j < strs.size(); j++)
从第二个字符串开始，依次遍历数组中的其他所有字符串，检查它们在第i个位置的字符。不匹配检测与返回：
if(i == strs[j].size() || tmp != strs[j][i])
这是代码中最关键的一步，判断当前列是否终止：i == strs[j].size()：这意味着字符串strs[j]的长度比i还要短（已经越界了）。既然某个字符串已经到头了，那公共前缀最远也就只能到i了。tmp != strs[j][i]：当前对比的字符与基准字符不同，说明公共前缀断了。如果满足上述任一条件，立刻返回
strs[0].substr(0, i)，即截取第一个字符串从 0 开始长度为i的部分，这正是当前找到的最长公共前缀。
循环结束返回：
return strs[0];
如果外层循环完整执行完毕，都没有触发内层的提前返回，说明第一个字符串strs[0]就是所有字符串的公共前缀，直接返回它即可。
复杂度分析
时间复杂度：O(N×M)。最坏情况下（所有字符串完全相同），需要比较每一个字符串的每一个字符。其中 N 是字符串数量，M 是字符串平均长度。
空间复杂度：O(1)（不计返回值占用的空间）。只使用了常数个额外变量。
算法对比（纵向扫描 vs 两两比较）
解法二：
优点：在发现不匹配时能尽早退出。例如输入是
["abcdefg", "abcde", "abc"]，当i=3（即比较第4个字符d时），内层循环发现i == strs[2].size()（长度为3，索引最大为2），立刻就能返回"abc"，不需要像两两比较那样每次都截取一遍字符串。在数据量大、差异出现早的情况下，效率往往更高。缺点：如果第一个字符串特别长，而其他字符串特别短，内层循环的越界判断会频繁触发。
解法一：
优点：思路极其直观，容易想到。
缺点：需要不断生成新的字符串对象（
substr会产生新对象），可能会有额外的性能开销。
题目二：最长回文子串
class Solution { public: string longestPalindrome(string s) { if (s.empty()) return ""; int begin = 0, len = 0; // 依次枚举所有的中点 for (int i = 0; i < s.size(); i++) { // 奇数长度 auto [l1, len1] = expandAroundCenter(s, i, i); // 偶数长度 auto [l2, len2] = expandAroundCenter(s, i, i + 1); if (len1 > len) { len = len1; begin = l1; } if (len2 > len) { len = len2; begin = l2; } } return s.substr(begin, len); } // 返回 {起始索引, 长度} 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) - (left + 1) + 1}; } };核心思想：中心扩展算法
回文串有一个天然的特性：它是对称的。因此，我们可以遍历字符串中的每一个字符，把它当作回文串的“中心”，然后向两边同时扩展，看看能扩展多长。
这里有一个关键点：回文串的长度可能是奇数，也可能是偶数。
奇数长度（如
"aba"）：中心是一个字符。偶数长度（如
"abba"）：中心是两个字符之间的“缝隙”。
这段代码正是分别处理了这两种情况。
复杂度分析
时间复杂度：O(N2)。其中 N 是字符串的长度。我们遍历了 N 个中心点，每个中心点向两边扩展最多需要 O(N)的时间。对于本题 N≤1000 的数据规模，O(N2) 是可以接受的（大约 100 万次操作）。
空间复杂度：O(1)。只使用了常数级别的额外变量，没有开辟与 N 相关的额外空间。
题目三：二进制求和
class Solution { public: string addBinary(string a, string b) { string ret; int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0; while (cur1 >= 0 || cur2 >= 0 || t) { if (cur1 >= 0) t += a[cur1--] - '0'; if (cur2 >= 0) t += b[cur2--] - '0'; ret += t % 2 + '0'; t /= 2; } reverse(ret.begin(), ret.end()); return ret; } };核心思想：模拟竖式加法（逢二进一）
十进制的加法是逢十进一，二进制则是逢二进一。我们需要从两个字符串的末尾（最低位）开始，依次向前遍历，逐位相加，并处理进位。
复杂度分析
时间复杂度：O(max(N,M))。其中 NN 和 MM 分别是字符串
a和b的长度。我们最多只需要遍历较长的那个字符串一次。空间复杂度：O(max(N,M))。主要消耗在存储结果字符串
ret上。如果不算返回值，额外的空间只有几个整型变量，是 O(1)。
题目四：字符串相乘
class Solution { public: string multiply(string num1, string num2) { int m = num1.size(), n = num2.size(); reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); vector<int> tmp(m + n - 1); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { tmp[i + j] += (num1[i] - '0') * (num2[j] - '0'); } } int cur = 0, t = 0; string ret; while (cur < m + n - 1 || t) { if (cur < m + n - 1) t += tmp[cur++]; ret += t % 10 + '0'; t /= 10; } while (ret.size() > 1 && ret.back() == '0') ret.pop_back(); reverse(ret.begin(), ret.end()); return ret; } };核心原理：坐标映射
假设有两个数字：
num1长度为m，反转后记为n1（索引i从 0 到m-1，代表从低位到高位）。num2长度为n，反转后记为n2（索引j从 0 到n-1，代表从低位到高位）。
在竖式乘法中，n1[i]和n2[j]相乘的结果，应该放在最终结果的第i + j位上。
为了避开复杂的进位处理，我们使用一个数组tmp来临时存储每个位置上的乘积之和（暂时不管进位）。
数组tmp的最大长度是多少？两个m位数和n位数相乘，结果最多是m + n位（比如 99 * 99 = 9801，2+2=4位）。
但因为i最大为m-1，j最大为n-1，所以i+j最大为m+n-2。因此，初始化tmp大小为m + n - 1就足够容纳所有累加结果了。
辅助理解图（无进位相乘累加阶段）：
1 2 3 (n1反转后是 3, 2, 1) x 4 5 6 (n2反转后是 6, 5, 4) ----------------- 18 15 12 (3分别乘6,5,4，放入tmp[0],tmp[1],tmp[2]) 27 22 8 (2分别乘6,5,4，放入tmp[1],tmp[2],tmp[3]) 28 13 4 (1分别乘6,5,4，放入tmp[2],tmp[3],tmp[4]) ----------------- 18 27 28 13 4 (这就是最终的tmp数组)注意：此时tmp数组里存的数字是“错位相加”的结果，还没有处理进位。
统一处理进位
现在我们得到了tmp = [18, 27, 28, 13, 4]。从左到右（从低位到高位）处理进位。
逻辑是：当前位的值 =tmp[cur] + 上一轮的进位。保留个位作为结果，十位作为进位传给下一位。
处理前导零并反转
ret = "88065"，末尾是'5'，没有多余的前导零。反转
ret得到"56088"。返回结果
"56088"。
复杂度分析
时间复杂度：O(M×N)。双重循环遍历了两个字符串的所有位。对于本题 M,N≤200M,N≤200，计算量大约在 4 万次左右，运行极快。
空间复杂度：O(M+N)。主要是
tmp数组和结果字符串ret占用的空间。
这段代码它将复杂的进位逻辑剥离了出来。如果我们在双层循环里直接处理进位，代码会变得异常复杂且容易出错（因为一个乘积可能会影响后面好几个位）。而“先全部乘完累加，最后统一处理进位”的思路，将问题分成了两个简单的子问题，大大降低了编码难度。
注意事项
写字符串代码时，90% 的 Bug 都出在以下细节上：
空字符串与边界检查
永远要先判断字符串是否为空（
s.empty()或s.length() == 0）。例如求最长公共前缀时，如果数组为空，直接访问strs[0]会导致程序崩溃。
索引与长度的“差一错误”
长度为
n的字符串，有效索引是0到n-1。在中心扩展算法中，循环结束后的真实回文长度通常是
right - left - 1，真实起始位置是left + 1，这里极容易算错。
字符与整数的转换
字符
'0'到'9'的 ASCII 码是连续的。数字字符转整数用c - '0'，整数转字符用n + '0'。判断字符是否为字母或数字，可以使用 C++ 内置函数
isalnum(c)、isdigit(c)、isalpha(c)。
字符串拼接的性能陷阱
在 C++ 中，
s = s + c在循环中会产生大量临时对象，导致时间复杂度退化到 O(N2)，容易超时。正确做法：使用
s += c或s.push_back(c)。如果是倒序生成的字符串（如大数运算），最后统一用reverse(s.begin(), s.end())反转。
善用内置函数，但别滥用
substrC++ 的
string提供了很多好用的函数，如find()、substr()、reverse()。但
substr()会创建新的字符串对象，在循环中频繁使用会导致性能下降。能用索引解决的就尽量用索引。
