[力扣] 剑指 Offer 第三天 - 左旋转字符串

耐心和持久胜过激烈和*。

题目来源

来源：力扣（LeetCode）

链接：​​https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof​​

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目描述

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

示例

示例 1

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

示例 2

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

题目分析

本题需要将字符串前面的若干个字符转移到字符串的尾部，由于在 Go 语言中，字符串不可变，因此需要创建一个新的字符串去实现。实现的方法有多种，如字符串切片拼接、字符串遍历拼接和字节切片拼接。

算法

字符串切片拼接

通过 ​​s[n:]​​ 和 ​​s[:n]​​ 获取两部分的字符串切片，使用 “+” 进行拼接即可。

代码实现

func reverseLeftWords(s string, n int) string {
    return s[n:] + s[:n]
}

复杂度分析

时间复杂度：O(N)，字符串切片函数使用了线性时间复杂度

空间复杂度：O(N)， N 为字符串的长度

字符串遍历拼接

• 定义一个空字符 ​​res​​ 变量
• 通过两个循环拼接反转后的字符串

• 第一个循环从下标为 ​​n​​ 开始拼接，直到末尾
• 第二个循环从下标为 ​​0​​ 开始到下标为 ​​n​​ 结束，继续拼接

• 返回结果

代码实现

func reverseLeftWords(s string, n int) string {
    res := ""
    for i := n; i < len(s); i++ {
        res += string(s[i])
    }
    for i := 0; i < n; i++ {
        res += string(s[i])
    }
    return res
}

巧用求余运算可以简化代码，只需一个 ​​for​​ 循环即可

func reverseLeftWords(s string, n int) string {
    res := ""
    for i := n; i < len(s) + n; i++ {
        res += string(s[i % len(s)])
    }
    return res
}

复杂度分析

时间复杂度：O(N)，需要循环与字符串长度相等的次数

空间复杂度：O(N)，拼接过程中会产生很多额外的空间，其中最大长度为 N，因此至少需要 O(N) 空间复杂度

字节切片拼接

• 定义一个 ​​strings.Builder​​ 变量，​​strings.Builder​​ 底层使用字节切片 ​​[]byte​​ 来保存字符
• 一个循环，从下标为 ​​n​​ 开始巧用求余运算拼接字符串
• 字节切片转字符串并返回结果

代码实现

func reverseLeftWords(s string, n int) string {
    var res strings.Builder
    for i := n; i < len(s) + n; i++ {
        res.WriteByte(s[i % len(s)])
    }
    return res.String()
}

复杂度分析

时间复杂度：O(N)，需要循环与字符串长度相等的次数

空间复杂度：O(N)，其中 N 为字节切片的长度

总结

第一种虽然代码看起来简洁，但是如果在面试中遇到这道题，用切片函数去实现字符串拼接，没有看点，个人觉得第三种方法是最好的，也是最高效的。

如果本文对你有帮助，欢迎点赞收藏加关注，如果本文有错误的地方，欢迎指正！