剑指offer--面试题 58 - II. 左旋转字符串

布满荆棘的人生 2023-02-19 09:25 9阅读 0赞

## 题目描述 ##

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

**示例 1：**

输入: s = “abcdefg”, k = 2  
输出: “cdefgab”

**示例 2：**

输入: s = “lrloseumgh”, k = 6  
输出: “umghlrlose”

**限制：**

1 <= k < s.length <= 10000

## 思路：字符串切片函数、列表遍历拼接、字符串遍历拼接 ##

## 考点: ##

字符串切片函数 substring()  
StringBuffer 的 append()方法 ，String的 charAt()方法  
**String+String 和StringBuffer.append()的区别**

## 解决方法 ##

**1. 切片法**  
**应用字符串切片函数**

class Solution {
        
        public String reverseLeftWords(String s, int n) {
        
            return s.substring(n) + s.substring(0,n);
            StringBuffer str = new StringBuffer();
        }
    }

**复杂度分析：**  
时间复杂度 O(N) ： 其中 N 为字符串 s 的长度，字符串切片函数为线性时间复杂度；  
空间复杂度 O(N) ： 两个字符串切片的总长度为 N 。

**2.列表遍历拼接 StringBuffer**

class Solution {
        
        public String reverseLeftWords(String s, int n) {
        
            StringBuffer str = new StringBuffer();
            for(int i=n; i<s.length(); i++){
        
                str.append(s.charAt(i));
            }
            for(int j=0; j<n; j++){
        
                str.append(s.charAt(j));
            }
            return str.toString();  //StringBuffer利用toString()方法输出
        }
    }

**复杂度分析：**  
时间复杂度 O(N） ： 线性遍历 s 并添加，使用线性时间；  
空间复杂度 O(N) ： 新建的辅助 res 使用 O(N) 大小的额外空间。

**3.字符串遍历拼接 String**

**此方法与 方法2 思路一致，区别是使用字符串代替列表。**

class Solution {
        
        public String reverseLeftWords(String s, int n) {
        
            //return s.substring(n) + s.substring(0,n);
            String str = "";
            for(int i=n; i<s.length(); i++){
        
                str += s.charAt(i);
            }
            for(int j=0; j<n; j++){
        
                str += s.charAt(j);
            }
            return str;
        }
    }

**复杂度分析：**  
时间复杂度 O(N) ： 线性遍历 s 并添加，使用线性时间；  
空间复杂度 O(N) ： 假设循环过程中内存会被及时回收，内存中至少同时存在长度为 N 和 N−1 的两个字符串（新建长度为 N 的 res 需要使用前一个长度 N−1 的 res ），因此至少使用 O(N) 的额外空间。