当前位置：首页 > news >正文

双指针算法实战：字符串翻转与右旋转精解

news 2026/8/4 1:47:36

1. 字符串操作实战：翻转单词与右旋转的算法精解

字符串处理是算法学习中最基础也最常考的核心技能。今天要拆解的两个题目——翻转字符串里的单词和右旋转字符串，看似简单却暗藏玄机。作为代码随想录算法训练营的经典题目，它们能帮助我们掌握双指针这一算法利器，同时培养对边界条件的敏感度。

我在刷题和面试辅导过程中发现，90%的初学者会在以下两个地方翻车：一是忽略连续空格的处理，二是右旋转次数大于字符串长度时不知如何优化。本文将用工业级的代码标准和实战调试经验，带你避开这些深坑。

2. 题目深度解析与解题思路

2.1 151.翻转字符串里的单词

题目要求将字符串中单词顺序翻转（注意不是反转每个字符），同时需要去除多余空格。例如：输入：" hello world " 输出："world hello"

关键难点在于：

首尾空格处理
单词间多个空格合并为一个
保持翻转后的单词本身不反转

2.2 卡码网55.右旋转字符串

题目要求将字符串右旋转k个字符。例如：输入："abcdefg", k=2 输出："fgabcde"

这里存在两个易错点：

当k大于字符串长度时的处理
空间复杂度优化（能否做到O(1)）

3. 双指针法的精妙运用

3.1 翻转字符串单词的三种解法对比

3.1.1 API解法（面试慎用）

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

虽然简洁，但面试时直接调库会显得准备不足，且split()的底层实现本身就是一个算法问题。

3.1.2 标准双指针解法

def reverseWords(s: str) -> str: # 1. 去除多余空格 def trim_spaces(s): left, right = 0, len(s) - 1 # 去掉首尾空格 while left <= right and s[left] == ' ': left += 1 while left <= right and s[right] == ' ': right -= 1 # 去掉中间多余空格 output = [] while left <= right: if s[left] != ' ': output.append(s[left]) elif output[-1] != ' ': output.append(s[left]) left += 1 return output # 2. 反转整个字符串 def reverse(l, left, right): while left < right: l[left], l[right] = l[right], l[left] left += 1 right -= 1 # 3. 反转每个单词 def reverse_each_word(l): start = end = 0 while start < len(l): while end < len(l) and l[end] != ' ': end += 1 reverse(l, start, end - 1) start = end + 1 end += 1 chars = trim_spaces(s) reverse(chars, 0, len(chars) - 1) reverse_each_word(chars) return ''.join(chars)

关键技巧：先整体反转再局部反转，可以避免使用额外空间。trim_spaces函数中的output[-1]检查是处理连续空格的核心。

3.2 右旋转字符串的工业级实现

3.2.1 常规解法（使用额外空间）

def rightRotateString(s: str, k: int) -> str: if not s: return s k %= len(s) # 处理k大于长度的情况 return s[-k:] + s[:-k]

3.2.2 原地操作解法（三次反转法）

def rightRotateString(s: str, k: int) -> str: def reverse(l, left, right): while left < right: l[left], l[right] = l[right], l[left] left += 1 right -= 1 arr = list(s) n = len(arr) k %= n reverse(arr, 0, n - 1) reverse(arr, 0, k - 1) reverse(arr, k, n - 1) return ''.join(arr)

算法原理：整体反转->前k个反转->剩余部分反转。时间复杂度O(n)，空间复杂度O(1)（假设语言支持原地修改字符串）

4. 边界条件与异常处理实战

4.1 翻转字符串的边界Case

全空格字符串：应返回空字符串
单个单词无空格：直接返回原字符串
前导/后置多个空格：需全部去除
单词间多个空格：保留一个

测试用例示例：

assert reverseWords(" hello world ") == "world hello" assert reverseWords("the sky is blue") == "blue is sky the" assert reverseWords(" ") == "" assert reverseWords("a") == "a"

4.2 右旋转的边界Case

k=0：返回原字符串
k=字符串长度：返回原字符串
k>字符串长度：取模运算
空字符串：直接返回

测试用例示例：

assert rightRotateString("abcdefg", 2) == "fgabcde" assert rightRotateString("abcdefg", 9) == "gabcdef" # 9%7=2 assert rightRotateString("", 3) == "" assert rightRotateString("abc", 0) == "abc"