左旋转字符串_牛客博客

题目的主要信息：

将给定字符串循环左移 $n$ 位
即最左边的 $n$ 位按照顺序整体接到右边末尾

举一反三：

学习完本题的思路你可以解决如下题目：

JZ5. 替换空格

JZ73. 翻转单词序列

方法一：三次反转（推荐使用）

思路：

循环左移相当于从第 $n$ 个位置开始，左右两部分视作整体翻转。即abcdefg左移3位defgabc可以看成AB翻转成BA（这里小写字母看成字符元素，大写字母看成整体）。既然是翻转我们就可以用到reverse函数。

具体做法:

step 1：因为 $n$ 可能大于字符串长度，因此需要对长度 $m$ 取余，因为每次长度为 $m$ 的旋转相当于没有变化。
step 2：第一次将整个字符串翻转，得到字符串的逆序，它已经满足了左移的整体出现在了右边。
step 3：第二次就将左边的 $m - n$ 个元素单独翻转，因为它虽然移到了左边，但是逆序了。
step 4：第三次就将右边的 $n$ 个元素单独翻转，因此这部分也逆序了。

图示：

alt

Java实现代码：

public class Solution {
    public String LeftRotateString(String str,int n) {
        //取余，因为每次长度为n的旋转数组相当于没有变化
        if(str.isEmpty() || str.length() == 0)
            return "";
        int m = str.length();
        n = n % m; 
        //第一次逆转全部元素
        char[] s = str.toCharArray();
        reverse(s, 0, m - 1); 
        //第二次只逆转开头m个
        reverse(s, 0, m - n - 1);
        //第三次只逆转结尾m个
        reverse(s, m - n, m - 1); 
        return new String(s);
    }
    //反转函数
    private void reverse(char[] s, int start, int end){ 
        while(start < end){
            swap(s, start++, end--);
        }
    }
    //交换函数
    private void swap(char[] s, int a, int b){ 
        char temp = s[a];
        s[a] = s[b];
        s[b] = temp;
    }
}

C++实现代码：

class Solution {
public:
    string LeftRotateString(string str, int n) {
        int m = str.length();
        //特殊情况
        if(m == 0)
            return "";
        //取余，因为每次长度为m的旋转相当于没有变化
        n = n % m; 
        //第一次逆转全部数组元素
        reverse(str.begin(), str.end()); 
        //第二次只逆转开头m个
        reverse(str.begin(), str.begin() + m - n); 
        //第三次只逆转结尾m个
        reverse(str.begin() + m - n, str.end()); 
        return str;
    }
};

Python实现代码：

class Solution:
    #反转函数
    def reverse(self, s: List, start: int, end: int):
        while start < end:
            self.swap(s, start, end)
            start += 1
            end -= 1
    #交换函数
    def swap(self, s: List, a: int, b: int):
        temp = s[a]
        s[a] = s[b]
        s[b] = temp
    
    def LeftRotateString(self , str: str, n: int) -> str:
        #取余，因为每次长度为n的旋转数组相当于没有变化
        s = list(str)
        m = len(s)
        if m == 0:
            return ""
        n = n % m 
        #第一次逆转全部元素
        self.reverse(s, 0, m - 1); 
        #第二次只逆转开头m个
        self.reverse(s, 0, m - n - 1)
        #第三次只逆转结尾m个
        self.reverse(s, m - n, m - 1) 
        return ''.join(s)

复杂度分析：

时间复杂度： $O (n)$ ，三次reverse函数的复杂度都最坏为 $O (n)$
空间复杂度： $O (1)$ ，C++没有使用额外的辅助空间，java与Python借助了 $O (n)$ 的空间

方法二：遍历拼接（扩展思路）

思路：

既然循环左移是前面 $n$ 个字符平移到了最后，我们就可以分开加入字符串中，先挨个加入后面部分字符，然后再回过头加入前面的字符。

具体做法：

step 1：因为 $n$ 可能大于字符串长度，因此需要对长度 $m$ 取余，因为每次长度为 $m$ 的旋转相当于没有变化。
step 2：先遍历后 $m - n$ 个字符，依次加入待返回的字符串中。
step 3：再遍历前 $n$ 个字符，依次加入待返回的字符串中。

Java实现代码：

import java.util.*;
public class Solution {
    public String LeftRotateString(String str,int n) {
        //取余，因为每次长度为n的旋转数组相当于没有变化
        if(str.isEmpty() || str.length() == 0)
            return "";
        int m = str.length();
        //取余，因为每次长度为m的旋转数组相当于没有变化
        n = n % m; 
        StringBuilder res = new StringBuilder();
        //先遍历后面的，放到前面
        for(int i = n; i < m; i++)
            res.append(str.charAt(i));
        //再遍历前面的放到后面
        for(int i = 0; i < n; i++)
            res.append(str.charAt(i));
        return res.toString();
    }
}

C++实现代码：

class Solution {
public:
    string LeftRotateString(string str, int n) {
        int m = str.length();
        //特殊情况
        if(m == 0)
            return "";
        //取余，因为每次长度为m的旋转数组相当于没有变化
        n = n % m; 
        string res = "";
        //先遍历后面的，放到前面
        for(int i = n; i < m; i++)
            res += str[i];
        //再遍历前面的放到后面
        for(int i = 0; i < n; i++)
            res += str[i];
        return res;
    }
};

Python实现代码：

class Solution:
    def LeftRotateString(self , str: str, n: int) -> str:
        m = len(str)
        #特殊情况
        if m == 0:
            return ""
        #取余，因为每次长度为m的旋转数组相当于没有变化
        n = n % m 
        res = ""
        #先遍历后面的，放到前面
        for i in range(n, m):
            res += str[i]
        #再遍历前面的放到后面
        for i in range(n):
            res += str[i]
        return res

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为字符串的长度，两次遍历相当于遍历整个字符串
空间复杂度： $O (1)$ ，res属于返回必要空间，无额外辅助空间