String - Sword finger offer 58 - ii Rotate string left

1 Title Description

The finger of the sword Offer 58 - II. Left rotation string

The left rotation operation of string is to transfer several characters in front of string to the end of string . Please define a function to implement the left rotation operation of string . such as , Input string "abcdefg" And number 2, This function will return the result of rotating two bits to the left "cdefgab".

2 Title Example

Example 1：
Input : s = “abcdefg”, k = 2
Output : “cdefgab”

Example 2：
Input : s = “lrloseumgh”, k = 6
Output : “umghlrlose”

3 Topic tips

1 <= k < s.length <= 10000

4 Ideas

There are many ways to solve this problem , This paper mainly introduces “ String slice ” , “ List traversal ” , “ String traversal splicing ” Three methods .
Because the multiple solutions of this problem involve The string is an immutable object Related concepts of , This leads to a great difference in efficiency . therefore , Make a separate section Efficiency analysis of three methods , Hope to help you .

Method 1 : String slice
Apply string slicing function , It is convenient to rotate the string left .
Get string s[n :] Slicing and s[:n] section , Use "+" Operator splice and return .
Complexity analysis :
Time complexity o(N): among N For the string s The length of , The string slicing function has linear time complexity ;
Spatial complexity o(N): The total length of the two string slices is N.

Method 2 : List traversal
If the interview rules do not allow the use of slicing functions , Use this method .
Algorithm flow :
1. Create a new one list(Python)、StringBuilder(Java), Write it down as res ;
2. First direction res add to “ The first n＋1 Characters from bit to last ”;
3. Again to res add to “ First to n A character ”;4. take res Convert to a string and return .
Complexity analysis :
Time complexity o(N): Linear traversal s And add , Use linear time ;.
Spatial complexity O(N)︰ New auxiliary res Use O(N) The size of the extra space

Method 3 : String traversal splicing
If specified Python Out of commission join( function , Or regulation Java Only use String, Use this method .
This method and method two train of thought — Cause , The difference is to use strings instead of lists .
Complexity analysis :
Time complexity o(N): Linear traversal s And add , Use linear time ;
Spatial complexity O(N): Suppose that the memory will be reclaimed in time during the cycle , There is at least a length of N and N―1 Two strings of ( New length is N Of res Previous length is required Ⅳ-1 Of res ) , So at least use O(N) Extra space .

5 My answer

Method 1 : String slice

class Solution {
    
    public String reverseLeftWords(String s, int n) {
    
        return s.substring(n, s.length()) + s.substring(0, n);
    }
}

Method 2 : List traversal

class Solution {
    
    public String reverseLeftWords(String s, int n) {
    
        StringBuilder res = new StringBuilder();
        for(int i = n; i < s.length(); i++)
            res.append(s.charAt(i));
        for(int i = 0; i < n; i++)
            res.append(s.charAt(i));
        return res.toString();
    }
}

Method 3 : String traversal splicing

class Solution {
    
    public String reverseLeftWords(String s, int n) {
    
        String res = "";
        for(int i = n; i < n + s.length(); i++)
            res += s.charAt(i % s.length());
        return res;
    }
}