1. 问题背景与需求分析151.反转字符串中的单词是LeetCode上一道经典的字符串处理题目。题目要求我们反转字符串中单词的顺序同时需要处理多余空格的问题。具体来说给定一个可能包含前导、尾随或单词间多个空格的字符串我们需要返回单词顺序反转且单词间用单个空格分隔的结果字符串。这道题看似简单但实际考察了多个字符串处理的核心能力字符串的遍历与操作空格处理与字符串分割数组/列表的反转操作字符串拼接的效率考量在实际编程面试中这类题目经常作为热身题出现。根据我的面试经验大约60%的候选人能写出基本解法但只有不到30%能给出最优解并解释清楚时空复杂度。这道题在2023年LeetCode周赛中出现过变种也是热门100题的常客。2. 核心解法思路拆解2.1 基础解法利用语言内置函数最直观的解法是利用编程语言提供的字符串处理函数def reverseWords(s: str) - str: return .join(reversed(s.split()))这种解法简洁明了但面试官通常会追问如果不允许使用split()和reversed()你会如何实现注意虽然这种解法代码简洁但在实际面试中直接调用高级API可能无法充分展示你的算法能力。建议掌握底层实现方法。2.2 手动实现的标准解法更符合面试要求的解法是手动实现整个过程去除首尾空格反转整个字符串反转每个单词处理单词间多余空格def reverseWords(s: str) - str: # 去除首尾空格 s s.strip() # 反转整个字符串 s list(s) n len(s) self.reverse(s, 0, n-1) # 反转每个单词并处理空格 i j 0 while i n: while j n and s[j] ! : j 1 self.reverse(s, i, j-1) # 处理多余空格 while j n and s[j] : j 1 i j # 处理单词间多余空格 slow fast 0 while fast n: if s[fast] ! : s[slow] s[fast] slow 1 elif slow 0 and s[slow-1] ! : s[slow] slow 1 fast 1 return .join(s[:slow]) def reverse(self, s, left, right): while left right: s[left], s[right] s[right], s[left] left 1 right - 12.3 双指针优化解法对于追求极致效率的场景可以使用双指针从后向前遍历def reverseWords(s: str) - str: res [] n len(s) i n - 1 while i 0: if s[i] : i - 1 continue j i while j 0 and s[j] ! : j - 1 res.append(s[j1:i1]) i j return .join(res)3. 复杂度分析与优化考量3.1 时间复杂度比较解法类型时间复杂度空间复杂度内置函数法O(n)O(n)手动实现法O(n)O(n)双指针法O(n)O(n)虽然三种解法的时间复杂度相同但实际性能有差异内置函数法实际最快因为底层用C实现双指针法避免了多次反转操作常数时间更优手动实现法代码量大但展示了完整思路3.2 语言特性考量不同语言实现时需要注意Python字符串不可变通常转为list处理JavaStringBuilder更高效C可以原地修改字符串以Java为例的优化实现public String reverseWords(String s) { StringBuilder sb new StringBuilder(); int end s.length() - 1; while (end 0) { if (s.charAt(end) ) { end--; continue; } int start end; while (start 0 s.charAt(start) ! ) { start--; } sb.append(s.substring(start 1, end 1)).append( ); end start; } return sb.toString().trim(); }4. 常见错误与边界情况4.1 典型错误案例未处理前导/尾随空格# 错误示例 def reverseWords(s: str) - str: words s.split( ) # 使用单个空格分割会保留空字符串 return .join(reversed([w for w in words if w]))多余空格处理不当# 错误示例 - 单词间可能仍有多个空格 def reverseWords(s: str) - str: s s.strip() return .join(reversed(s.split()))原地修改时的索引错误# 错误示例 - 反转时索引处理不当 def reverse(s, left, right): while left right: s[left], s[right] s[right], s[left] left 1 # 缺少right - 14.2 边界测试用例必须测试的边界情况全空格字符串 单个单词hello前后有空格 hello world 单词间多个空格a good example超长字符串性能测试5. 实际应用与变种题目5.1 工程应用场景这种字符串处理技术在以下场景有实际应用搜索引擎的查询预处理文本编辑器的格式整理日志处理系统的信息提取自然语言处理的预处理阶段5.2 相关变种题目反转字符串IILeetCode 541每隔2k字符反转前k个反转字符串中的元音LeetCode 345只反转元音字母旋转字符串LeetCode 796检查是否可以通过旋转得到反转单词顺序列剑指Offer 58-I类似本题5.3 面试技巧在面试中遇到此类题目时先确认输入输出要求是否原地修改、空格处理等提出暴力解法并分析复杂度逐步优化解释每个优化点的考虑主动提出测试用例特别是边界情况讨论可能的实际应用场景6. 性能优化进阶对于特别大的字符串如处理整个文档可以考虑分块处理将字符串分成适当大小的块分别处理并行处理对不同的单词块使用多线程反转内存映射对于极大文件使用内存映射文件技术C示例的分块处理std::string reverseWords(std::string s) { std::reverse(s.begin(), s.end()); int storeIndex 0; for (int i 0; i s.size(); i) { if (s[i] ! ) { if (storeIndex ! 0) s[storeIndex] ; int j i; while (j s.size() s[j] ! ) s[storeIndex] s[j]; std::reverse(s.begin() storeIndex - (j - i), s.begin() storeIndex); i j; } } s.erase(s.begin() storeIndex, s.end()); return s; }7. 语言特定实现技巧7.1 Python优化技巧使用列表推导式更简洁def reverseWords(s: str) - str: return .join([word for word in reversed(s.split())])使用re模块处理复杂空格import re def reverseWords(s: str) - str: return .join(reversed(re.split(r\s, s.strip())))7.2 Java注意事项使用StringBuilder而非String拼接注意trim()和split()的性能开销考虑使用StringTokenizer已过时但面试中可能讨论7.3 C实现要点使用std::reverse进行原地反转注意字符串的erase操作效率考虑使用istringstream进行单词分割8. 测试与验证方法8.1 单元测试编写完善的测试应包含import unittest class TestReverseWords(unittest.TestCase): def test_normal_case(self): self.assertEqual(reverseWords(the sky is blue), blue is sky the) def test_leading_trailing_spaces(self): self.assertEqual(reverseWords( hello world ), world hello) def test_multiple_spaces(self): self.assertEqual(reverseWords(a good example), example good a) def test_single_word(self): self.assertEqual(reverseWords(hello), hello) def test_empty_string(self): self.assertEqual(reverseWords(), ) if __name__ __main__: unittest.main()8.2 性能测试方法对于大规模字符串的性能测试import time def test_performance(): # 生成超长测试字符串 long_str .join([word] * 1000000) start time.time() reverseWords(long_str) end time.time() print(fProcessing 1,000,000 words took: {end-start:.2f} seconds)9. 学习路径建议要系统掌握这类字符串处理问题建议先掌握基本的字符串操作遍历、切片、拼接常用方法split, join, strip等练习相关基础题目反转字符串LeetCode 344反转字符串IILeetCode 541反转元音字母LeetCode 345进阶到更复杂问题字符串解码LeetCode 394字符串转换整数LeetCode 8有效的字母异位词LeetCode 242最后挑战综合应用字符串相乘LeetCode 43简化路径LeetCode 71文本对齐LeetCode 68 
长河君 · 2026/8/4 10:53:46 · 阅读 1.2k LeetCode 151：字符串单词反转的算法实现与优化
1. 问题背景与需求分析151.反转字符串中的单词是LeetCode上一道经典的字符串处理题目。题目要求我们反转字符串中单词的顺序同时需要处理多余空格的问题。具体来说给定一个可能包含前导、尾随或单词间多个空格的字符串我们需要返回单词顺序反转且单词间用单个空格分隔的结果字符串。这道题看似简单但实际考察了多个字符串处理的核心能力字符串的遍历与操作空格处理与字符串分割数组/列表的反转操作字符串拼接的效率考量在实际编程面试中这类题目经常作为热身题出现。根据我的面试经验大约60%的候选人能写出基本解法但只有不到30%能给出最优解并解释清楚时空复杂度。这道题在2023年LeetCode周赛中出现过变种也是热门100题的常客。2. 核心解法思路拆解2.1 基础解法利用语言内置函数最直观的解法是利用编程语言提供的字符串处理函数def reverseWords(s: str) - str: return .join(reversed(s.split()))这种解法简洁明了但面试官通常会追问如果不允许使用split()和reversed()你会如何实现注意虽然这种解法代码简洁但在实际面试中直接调用高级API可能无法充分展示你的算法能力。建议掌握底层实现方法。2.2 手动实现的标准解法更符合面试要求的解法是手动实现整个过程去除首尾空格反转整个字符串反转每个单词处理单词间多余空格def reverseWords(s: str) - str: # 去除首尾空格 s s.strip() # 反转整个字符串 s list(s) n len(s) self.reverse(s, 0, n-1) # 反转每个单词并处理空格 i j 0 while i n: while j n and s[j] ! : j 1 self.reverse(s, i, j-1) # 处理多余空格 while j n and s[j] : j 1 i j # 处理单词间多余空格 slow fast 0 while fast n: if s[fast] ! : s[slow] s[fast] slow 1 elif slow 0 and s[slow-1] ! : s[slow] slow 1 fast 1 return .join(s[:slow]) def reverse(self, s, left, right): while left right: s[left], s[right] s[right], s[left] left 1 right - 12.3 双指针优化解法对于追求极致效率的场景可以使用双指针从后向前遍历def reverseWords(s: str) - str: res [] n len(s) i n - 1 while i 0: if s[i] : i - 1 continue j i while j 0 and s[j] ! : j - 1 res.append(s[j1:i1]) i j return .join(res)3. 复杂度分析与优化考量3.1 时间复杂度比较解法类型时间复杂度空间复杂度内置函数法O(n)O(n)手动实现法O(n)O(n)双指针法O(n)O(n)虽然三种解法的时间复杂度相同但实际性能有差异内置函数法实际最快因为底层用C实现双指针法避免了多次反转操作常数时间更优手动实现法代码量大但展示了完整思路3.2 语言特性考量不同语言实现时需要注意Python字符串不可变通常转为list处理JavaStringBuilder更高效C可以原地修改字符串以Java为例的优化实现public String reverseWords(String s) { StringBuilder sb new StringBuilder(); int end s.length() - 1; while (end 0) { if (s.charAt(end) ) { end--; continue; } int start end; while (start 0 s.charAt(start) ! ) { start--; } sb.append(s.substring(start 1, end 1)).append( ); end start; } return sb.toString().trim(); }4. 常见错误与边界情况4.1 典型错误案例未处理前导/尾随空格# 错误示例 def reverseWords(s: str) - str: words s.split( ) # 使用单个空格分割会保留空字符串 return .join(reversed([w for w in words if w]))多余空格处理不当# 错误示例 - 单词间可能仍有多个空格 def reverseWords(s: str) - str: s s.strip() return .join(reversed(s.split()))原地修改时的索引错误# 错误示例 - 反转时索引处理不当 def reverse(s, left, right): while left right: s[left], s[right] s[right], s[left] left 1 # 缺少right - 14.2 边界测试用例必须测试的边界情况全空格字符串 单个单词hello前后有空格 hello world 单词间多个空格a good example超长字符串性能测试5. 实际应用与变种题目5.1 工程应用场景这种字符串处理技术在以下场景有实际应用搜索引擎的查询预处理文本编辑器的格式整理日志处理系统的信息提取自然语言处理的预处理阶段5.2 相关变种题目反转字符串IILeetCode 541每隔2k字符反转前k个反转字符串中的元音LeetCode 345只反转元音字母旋转字符串LeetCode 796检查是否可以通过旋转得到反转单词顺序列剑指Offer 58-I类似本题5.3 面试技巧在面试中遇到此类题目时先确认输入输出要求是否原地修改、空格处理等提出暴力解法并分析复杂度逐步优化解释每个优化点的考虑主动提出测试用例特别是边界情况讨论可能的实际应用场景6. 性能优化进阶对于特别大的字符串如处理整个文档可以考虑分块处理将字符串分成适当大小的块分别处理并行处理对不同的单词块使用多线程反转内存映射对于极大文件使用内存映射文件技术C示例的分块处理std::string reverseWords(std::string s) { std::reverse(s.begin(), s.end()); int storeIndex 0; for (int i 0; i s.size(); i) { if (s[i] ! ) { if (storeIndex ! 0) s[storeIndex] ; int j i; while (j s.size() s[j] ! ) s[storeIndex] s[j]; std::reverse(s.begin() storeIndex - (j - i), s.begin() storeIndex); i j; } } s.erase(s.begin() storeIndex, s.end()); return s; }7. 语言特定实现技巧7.1 Python优化技巧使用列表推导式更简洁def reverseWords(s: str) - str: return .join([word for word in reversed(s.split())])使用re模块处理复杂空格import re def reverseWords(s: str) - str: return .join(reversed(re.split(r\s, s.strip())))7.2 Java注意事项使用StringBuilder而非String拼接注意trim()和split()的性能开销考虑使用StringTokenizer已过时但面试中可能讨论7.3 C实现要点使用std::reverse进行原地反转注意字符串的erase操作效率考虑使用istringstream进行单词分割8. 测试与验证方法8.1 单元测试编写完善的测试应包含import unittest class TestReverseWords(unittest.TestCase): def test_normal_case(self): self.assertEqual(reverseWords(the sky is blue), blue is sky the) def test_leading_trailing_spaces(self): self.assertEqual(reverseWords( hello world ), world hello) def test_multiple_spaces(self): self.assertEqual(reverseWords(a good example), example good a) def test_single_word(self): self.assertEqual(reverseWords(hello), hello) def test_empty_string(self): self.assertEqual(reverseWords(), ) if __name__ __main__: unittest.main()8.2 性能测试方法对于大规模字符串的性能测试import time def test_performance(): # 生成超长测试字符串 long_str .join([word] * 1000000) start time.time() reverseWords(long_str) end time.time() print(fProcessing 1,000,000 words took: {end-start:.2f} seconds)9. 学习路径建议要系统掌握这类字符串处理问题建议先掌握基本的字符串操作遍历、切片、拼接常用方法split, join, strip等练习相关基础题目反转字符串LeetCode 344反转字符串IILeetCode 541反转元音字母LeetCode 345进阶到更复杂问题字符串解码LeetCode 394字符串转换整数LeetCode 8有效的字母异位词LeetCode 242最后挑战综合应用字符串相乘LeetCode 43简化路径LeetCode 71文本对齐LeetCode 68