剑指 Offer 58 - II: 左旋转字符串

[songyy5517]

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：

输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

分析 这道题考察的是字符串的遍历和拼接。这道题涉及到字符串的分割，我们可以通过取余操作实现字符串的左旋转。

[songyy5517]

思路1：字符串切片

1. 异常处理；
2. 切片 & 拼接；
3. 返回新字符串。

复杂度分析

• 时间复杂度： $O(N)$ ，N为字符串长度，切片为线性复杂度。
• 空间复杂度： $O(N)$ ，返回的新字符串占用 $O(N)$ 大小的空间。

思路2：字符串遍历拷贝，取余实现左旋转

1. 异常处理；
2. 定义StringBuilder存放新字符串；
3. 从位置n开始向后遍历字符串，然后从头遍历0到n的片段，将字符放入StringBuilder当中；
4. 返回新字符串。

复杂度分析

• 时间复杂度： $O(N)$ ，N为字符串长度，遍历字符串为线性复杂度。
• 空间复杂度： $O(N)$ ，额外定义的StringBuilder占用 $O(N)$ 大小的空间。

[songyy5517]

class Solution {
    public String reverseLeftWords(String s, int n) {
        // 思路1：字符串切片
        // 1. 异常处理
        if (s == null || s.length() == 0 || n <= 0 || n > s.length())
            return s;

        return s.substring(n, s.length()) + s.substring(0, n);
    }
}

class Solution {
    public String reverseLeftWords(String s, int n) {
        // 思路2：遍历拼接
        // 1. 异常处理
        if (s == null || s.length() == 0 || n <= 0 || n > s.length())
            return s;

        // 2. 定义
        StringBuilder res = new StringBuilder();
        for (int i = n; i < n + s.length(); i++){
            res.append(s.charAt(i % s.length()));
        }

        return res.toString();
    }
}

[songyy5517]

2023/12/2 2024/3/15

• 遍历，StringBuffer拼接，取余实现左旋转。

2024/3/25