文章

[LeetCode] 每日一题 541. 反转字符串 II

题目链接

https://leetcode.cn/problems/reverse-string-ii

题目描述

给定一个字符串 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

解题思路

本题属于基础的字符串操作题目,要求按照特定规则对字符串进行局部反转。遍历字符串时,每次处理 2k 个字符,并反转其中的前 k 个字符。同时,需要根据剩余字符数量调整反转方式:

  • 如果剩余字符少于 k,则全部反转

  • 如果剩余字符在 k2k 之间,则仅反转前 k 个字符,其余部分保持不变

为了实现这一规则,我们可以:

  1. 使用 for 循环,每次步长为 2k,从 0 开始遍历整个字符串,这样能直观地定位每个需要处理的区间,避免额外的索引维护

  2. 将反转逻辑封装到一个独立方法中,提高代码的可读性和复用性,同时符合软件工程中的单一职责原则(SRP),使代码结构更加清晰

代码实现

class Solution {
    public String reverseStr(String s, int k) {
        char[] ansArray = s.toCharArray();
        for (int i = 0; i < s.length(); i += 2 * k) {
            reverse(ansArray, i, Math.min(i + k - 1, s.length() - 1));
        }
        return new String(ansArray);
    }

    private void reverse(char[] array, int start, int end) {
        while (start < end) {
            char temp = array[start];
            array[start] = array[end];
            array[end] = temp;
            start++;
            end--;
        }
    }
}

复杂度分析

  • 时间复杂度:O(n),其中 n 是字符串 s 的长度。每 2k 个字符处理一次,每次最多反转 k 个字符,因此整个字符串的反转操作仍是线性复杂度

  • 空间复杂度:O(n),主要是由于字符串 s 转换为字符数组 char[] 进行操作,但不包含额外的数据结构,因此为 O(n)。如果允许直接修改字符串(如 Python 或 C++),可以优化为 O(1) 额外空间

总结

本题的核心是按规则分段处理字符串,并进行局部反转。通过 for 循环遍历字符串,每次步长 2k,可以更直观地维护索引,避免 while 方式的复杂性。封装反转逻辑至独立方法,有助于提高代码的复用性和可读性。这种分段遍历 + 局部操作的思想在字符串处理类题目中非常常见,是一个值得掌握的技巧

希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。

License:  CC BY 4.0