跳转至

541. 反转字符串 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 <= 104
  • s 仅由小写英文组成
  • 1 <= k <= 104

解法

方法一：双指针

我们可以遍历字符串 $\textit{s}$，每次遍历 $\textit{2k}$ 个字符，然后利用双指针技巧，对这 $\textit{2k}$ 个字符中的前 $\textit{k}$ 个字符进行反转。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $\textit{s}$ 的长度。

1
2
3
4
5
6
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        cs = list(s)
        for i in range(0, len(cs), 2 * k):
            cs[i : i + k] = reversed(cs[i : i + k])
        return "".join(cs)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public String reverseStr(String s, int k) {
        char[] cs = s.toCharArray();
        int n = cs.length;
        for (int i = 0; i < n; i += k * 2) {
            for (int l = i, r = Math.min(i + k - 1, n - 1); l < r; ++l, --r) {
                char t = cs[l];
                cs[l] = cs[r];
                cs[r] = t;
            }
        }
        return new String(cs);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.size();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(s.begin() + i, s.begin() + min(i + k, n));
        }
        return s;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func reverseStr(s string, k int) string {
    cs := []byte(s)
    n := len(cs)
    for i := 0; i < n; i += 2 * k {
        for l, r := i, min(i+k-1, n-1); l < r; l, r = l+1, r-1 {
            cs[l], cs[r] = cs[r], cs[l]
        }
    }
    return string(cs)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function reverseStr(s: string, k: number): string {
    const n = s.length;
    const cs = s.split('');
    for (let i = 0; i < n; i += 2 * k) {
        for (let l = i, r = Math.min(i + k - 1, n - 1); l < r; l++, r--) {
            [cs[l], cs[r]] = [cs[r], cs[l]];
        }
    }
    return cs.join('');
}

评论