【Leetcode】随笔

LeetCode 高频“字符串操作”题通关：3道题教你玩转字符处理

🌈 你好呀！我是 山顶风景独好
🎈 字符串题是算法面试的“常客”，看似简单，实则暗藏诸多细节陷阱——比如字符编码、边界越界、效率优化等。很多人写字符串处理代码要么漏洞百出，要么效率低下。本文精选3道高频字符串题，拆解“常规思路→优化技巧→细节把控”的全过程，帮你练就字符串处理的“硬核能力”。

一、 最长回文子串（LeetCode 5，中等）—— 中心扩展法的高效应用

题目痛点

这道题的暴力思路是“枚举所有子串，判断是否回文”，但时间复杂度高达O ( n 3 ) O(n^3)O(n3)，完全无法通过中等规模的测试用例；而动态规划解法虽然能将时间复杂度降至O ( n 2 ) O(n^2)O(n2)，但空间复杂度也达到了O ( n 2 ) O(n^2)O(n2)。中心扩展法则能在O ( n 2 ) O(n^2)O(n2)时间、O ( 1 ) O(1)O(1)空间内解决问题，是性价比最高的解法。

题目回顾

给你一个字符串s，找到s中最长的回文子串。
示例：输入s = "babad"→ 输出"bab"或"aba"；输入s = "cbbd"→ 输出"bb"。

常规思路的局限性

1. 暴力枚举：枚举所有子串的起始和结束索引，判断是否回文。枚举子串的时间是O ( n 2 ) O(n^2)O(n2)，判断回文的时间是O ( n ) O(n)O(n)，总时间复杂度O ( n 3 ) O(n^3)O(n3)。
2. 动态规划：定义dp[i][j]表示子串s[i..j]是否为回文串。状态转移方程为：
   d p [ i ] [ j ] = ( s [ i ] = = s [ j ] ) a n d d p [ i + 1 ] [ j − 1 ] dp[i][j] = (s[i] == s[j]) \quad and \quad dp[i+1][j-1]dp[i][j]=(s[i]==s[j])anddp[i+1][j−1]
   边界条件：dp[i][i] = true（单个字符是回文），dp[i][i+1] = (s[i] == s[i+1])（两个相同字符是回文）。
   这种方法的空间复杂度为O ( n 2 ) O(n^2)O(n2)，当n=1e3时，内存占用就会超标。

优化技巧：中心扩展法

核心洞察：回文串的本质是对称性——每个回文串都有一个“中心”，可以是一个字符（对应奇数长度回文，如"aba"的中心是b），也可以是两个字符之间的间隙（对应偶数长度回文，如"abba"的中心是两个b之间）。

基于这个洞察，算法思路如下：

1. 遍历字符串中的每个字符，分别以该字符为奇数长度回文的中心，向左右扩展，记录最长回文子串；
2. 遍历字符串中的每对相邻字符，以它们之间的间隙为偶数长度回文的中心，向左右扩展，记录最长回文子串；
3. 最终取所有扩展结果中的最大值。

完整代码实现

deflongestPalindrome(s:str)->str:n=len(s)ifn<2:returns start,max_len=0,1# 最长回文子串的起始索引和长度defexpand(left:int,right:int)->tuple[int,int]:""" 从中心向左右扩展，返回回文子串的起始索引和长度 """whileleft>=0andright<nands[left]==s[right]:left-=1right+=1# 退出循环时，s[left] != s[right]，所以有效长度是 right-left-1returnleft+1,right-left-1foriinrange(n):# 奇数长度回文：中心是s[i]l1,len1=expand(i,i)# 偶数长度回文：中心是s[i]和s[i+1]之间l2,len2=expand(i,i+1)# 更新最长回文子串信息current_max=max(len1,len2)ifcurrent_max>max_len:max_len=current_max start=l1iflen1>len2elsel2returns[start:start+max_len]# 测试用例print(longestPalindrome("babad"))# 输出 bab 或 abaprint(longestPalindrome("cbbd"))# 输出 bbprint(longestPalindrome("a"))# 输出 a

思维提炼

处理回文串问题时，优先考虑中心扩展法——相比动态规划，它省去了O ( n 2 ) O(n^2)O(n2)的空间开销；相比暴力枚举，它的时间效率更高。同时，要注意区分奇数和偶数长度的回文中心，避免遗漏情况。

二、 字符串相乘（LeetCode 43，中等）—— 模拟竖式乘法的细节把控

题目痛点

这道题的常规思路是“转整数相乘再转回字符串”，但当字符串长度超过 20 时，整数就会溢出；而模拟竖式乘法时，又容易在进位处理和结果拼接上出错。核心难点是“如何用字符串精准模拟人工乘法的每一步”。

题目回顾

给定两个以字符串形式表示的非负整数num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或常规的行之有效的

常规思路的死胡同

直接将num1和num2转为整数相乘：

defmultiply_naive(num1:str,num2:str)->str:returnstr(int(num1)*int(num2))

这种方法在num1或num2长度超过 20 时，会因整数溢出而失效，完全不符合题目要求。

优化技巧：模拟竖式乘法

核心洞察：人工计算乘法的步骤是“逐位相乘→错位相加→处理进位”，我们可以用数组模拟这个过程：

1. 结果长度分析：两个长度分别为m和n的数相乘，结果的长度最多为m + n（如99 * 99 = 9801，长度 2+2=4）。因此，我们可以初始化一个长度为m + n的数组res存储中间结果。
2. 逐位相乘：遍历num1的每一位（从后往前）和num2的每一位（从后往前），计算乘积，将结果加到res[i + j + 1]的位置（i和j分别是两个数的当前位索引）。
3. 处理进位：从后往前遍历res数组，将每位的数值对 10 取余得到当前位，除以 10 得到进位，加到前一位。
4. 结果拼接：去除res数组开头的零，转为字符串；若结果全零，则返回"0"。

完整代码实现

defmultiply(num1:str,num2:str)->str:ifnum1=="0"ornum2=="0":return"0"m,n=len(num1),len(num2)# 初始化结果数组，长度为m+n，初始值为0res=[0]*(m+n)# 从后往前遍历num1和num2的每一位foriinrange(m-1,-1,-1):digit1=int(num1[i])forjinrange(n-1,-1,-1):digit2=int(num2[j])# 乘积加到对应位置res[i+j+1]+=digit1*digit2# 处理进位forkinrange(m+n-1,0,-1):carry=res[k]//10res[k-1]+=carry res[k]=res[k]%10# 去除开头的零start=0whilestart<m+nandres[start]==0:start+=1# 转为字符串return''.join(map(str,res[start:]))# 测试用例print(multiply("2","3"))# 输出 6print(multiply("123","456"))# 输出 56088print(multiply("0","12345"))# 输出 0

思维提炼

处理大数相乘问题时，必须用模拟竖式乘法的方法，避免整数溢出。核心是“用数组存储中间结果”，并注意三个细节：

1. 乘积的位置对应关系（res[i+j+1]）；
2. 进位的处理顺序（从后往前）；
3. 结果前导零的去除。

三、 翻转字符串里的单词（LeetCode 151，中等）—— 双指针的高效处理

题目痛点

这道题的常规思路是“split 分割→反转列表→join 拼接”，但题目往往会附加限制条件（如“不允许使用额外空间”“字符串首尾和中间有多个空格”），此时常规方法就会失效。核心难点是“在原字符串上高效处理空格和翻转”。

题目回顾

给你一个字符串s，逐个翻转字符串中的每个单词。单词是由非空格字符组成的字符串，s中

可能包含前导空格、尾随空格和单词间的多个空格。返回的结果字符串中，单词间只能用单个空格分隔，且不包含任何额外空格。
示例：输入s = "the sky is blue"→ 输出"blue is sky the"；输入s = " hello world "→ 输出"world hello"。

常规思路的局限性

用 Python 内置函数处理：

defreverseWords_naive(s:str)->str:return' '.join(reversed(s.split()))

这种方法虽然简洁，但不符合“不允许使用额外空间”的进阶要求，且无法体现算法能力。

优化技巧：双指针+原地翻转

核心洞察：要在O ( 1 ) O(1)O(1)额外空间内解决问题（Python 中字符串不可变，需转为列表），可以分三步：

1. 去除多余空格：用双指针法，将字符串中的多余空格（前导、尾随、中间多个）去除，只保留单词间的单个空格；
2. 翻转整个字符串：将整个字符串的字符顺序反转；
3. 翻转每个单词：遍历字符串，找到每个单词的边界，将每个单词单独反转。

完整代码实现

defreverseWords(s:str)->str:# 转为列表，方便原地修改chars=list(s)n=len(chars)# 步骤1：去除多余空格slow=0forfastinrange(n):# 跳过空格ifchars[fast]==' ':continue# 单词间添加单个空格ifslow!=0:chars[slow]=' 'slow+=1# 复制当前单词的字符whilefast<nandchars[fast]!=' ':chars[slow]=chars[fast]slow+=1fast+=1# 此时slow是去除多余空格后的字符串长度chars=chars[:slow]m=len(chars)# 步骤2：翻转整个字符串defreverse(left:int,right:int):whileleft<right:chars[left],chars[right]=chars[right],chars[left]left+=1right-=1reverse(0,m-1)# 步骤3：翻转每个单词start=0foriinrange(m):ifchars[i]==' ':reverse(start,i-1)start=i+1# 翻转最后一个单词reverse(start,m-1)return''.join(chars)# 测试用例print(reverseWords("the sky is blue"))# 输出 blue is sky theprint(reverseWords(" hello world "))# 输出 world helloprint(reverseWords("a good example"))# 输出 example good a

思维提炼

处理字符串翻转、去空格等问题时，双指针法是首选——它能在O ( n ) O(n)O(n)时间、O ( 1 ) O(1)O(1)额外空间内完成操作。同时，“先整体翻转，再局部翻转”的技巧，是解决“单词翻转”类问题的通用套路。

总结：字符串题的解题通用心法

1. 回文问题选中心扩展：避免动态规划的空间开销，精准利用回文的对称性；
2. 大数问题选模拟竖式：杜绝整数溢出，逐位处理进位和拼接；
3. 翻转去空格选双指针：实现原地操作，兼顾时间和空间效率。

字符串题的本质是细节把控——字符的索引、空格的处理、进位的计算，每一个细节都可能导致代码出错。只有掌握了底层的处理技巧，才能应对各种附加限制条件，写出高效且严谨的代码。

🏠 更多字符串算法题解析，欢迎到我的CSDN主页交流：山顶风景独好
✨ 如果你遇到“字符串处理无从下手”的算法题，随时告诉我，一起拆解解题思路！