541. 反转字符串 II

🟢   🔖  双指针 字符串  🔗 力扣 LeetCode

题目

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.

Example 1:

Input: s = "abcdefg", k = 2

Output: "bacdfeg"

Example 2:

Input: s = "abcd", k = 2

Output: "bacd"

Constraints:

• 1 <= s.length <= 10^4
• s consists of only lowercase English letters.
• 1 <= k <= 10^4

题目大意

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入： s = "abcdefg", k = 2

输出： "bacdfeg"

示例 2：

输入： s = "abcd", k = 2

输出： "bacd"

提示：

• 1 <= s.length <= 10^4
• s 仅由小写英文组成
• 1 <= k <= 10^4

解题思路

1. 将字符串转为数组，以便原地修改字符。
2. 使用 for 循环，步长为 2k，遍历字符串，从 0 开始处理每个子段，翻转前 k 个字符：
   • 计算当前子段的翻转范围 [start, min(start + k - 1, s.length - 1)]。
   • 使用双指针，i 从子段的开头，j 从子段的末尾，逐步交换字符。
3. 将处理后的数组转换回字符串并返回。

复杂度分析

• 时间复杂度：O(n)
  • 遍历字符串，每次处理最多 2k 个字符，时间复杂度为 O(n)；
  • 数组转换和拼接的时间复杂度也是 O(n)。
• 空间复杂度：O(n)，转换字符串为数组，存储字符数组的开销。

代码

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var reverseStr = function (s, k) {
	let arr = s.split(''); // 将字符串转为数组
	for (let start = 0; start < s.length; start += 2 * k) {
		// 每次处理 2k 个字符
		let i = start; // 翻转区间的起始索引
		let j = Math.min(start + k - 1, s.length - 1); // 翻转区间的结束索引（不要越界）
		// 翻转区间内的字符
		while (i < j) {
			let temp = arr[i];
			arr[i++] = arr[j];
			arr[j--] = temp;
		}
	}
	return arr.join(''); // 返回翻转后的字符串
};

相关题目

题号	标题	题解	标签	难度	力扣
344	反转字符串	[✓]	双指针 字符串	🟢	🀄️ 🔗
557	反转字符串中的单词 III	[✓]	双指针 字符串	🟢	🀄️ 🔗
2810	故障键盘		字符串 模拟	🟢	🀄️ 🔗