String -- 344. Reverse string

1 Title Description

344. Reverse string

Write a function , Its function is to invert the input string . Input string as character array s Given in the form of .

Do not allocate extra space to another array , You have to modify the input array in place 、 Use O(1) To solve this problem .

2 Title Example

Example 1：
Input ：s = [“h”,“e”,“l”,“l”,“o”]
Output ：[“o”,“l”,“l”,“e”,“h”]

Example 2：
Input ：s = [“H”,“a”,“n”,“n”,“a”,“h”]
Output ：[“h”,“a”,“n”,“n”,“a”,“H”]

3 Topic tips

1 <= s.length <= 105
s[i] All are ASCII Printable characters in code table

4 Ideas

For length is N The array of characters to be reversed , We can observe the change of subscript before and after inversion , Suppose the array of characters before inversion is s[o] s[1] s[2] … sLN- 1], So the inverted character array is s[N - 1] s[N - 2] …s[o]. Comparing the change of subscript before and after inversion, it is easy to get s[i] The characters of and s[N - 1 - i] There is a law of character exchange , So we can get the following solution of double pointer :

• take 1eft Point to the first element of the character array ,right Points to the end element of the character array .
• When 1eft < right :
  • In exchange for s[1eft] and s[right] ;
  • left Move the pointer one bit to the right , namely 1eft = left + 1 ;
  • right Move the pointer one bit to the left , namely right = right - 1.
• When 1eft >= right , flip end , Return the character array .
  
  Complexity analysis

Time complexity ：O(N)O(N), among NN Is the length of the character array . All executed N/2N/2 Exchange of times .
Spatial complexity ：O(1)O(1). Only constant space is used to store several variables .

5 My answer

class Solution {
    
    public void reverseString(char[] s) {
    
        int n = s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
    
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
        }
    }
}