This series of questions is taken from LeetCode’s list of TOP interview questions: leetcode-cn.com/problemset/…

Topic describes

Original link: leetcode-cn.com/problems/re…

Write a function that reverses the input string. The input string is given in the form of the character array char[].

Instead of allocating extra space to another array, you must modify the input array in place, using O(1) extra space to solve the problem.

You can assume that all the characters in the array are printable characters in the ASCII code table.

Example 1:

Input:"h"."e"."l"."l"."o"] output: ["o"."l"."l"."e"."h"]
Copy the code

Example 2:

Input:"H"."a"."n"."n"."a"."h"] output: ["h"."a"."n"."n"."a"."H"]
Copy the code

Their thinking

Since the space complexity required by the problem is O(1), that is, no extra space can be used, we consider using the double pointer + loop swap method to solve the problem.

[“h”,”e”,”l”,”l”,”o”];

Swap the characters pointed to by I and j:

After the exchange, you get the string [” O “,”e”,” L “,” L “,” H “]. Move I one bit to the right and j one bit to the left:

At this point, I points to character e and j to character L, continuing to swap the two:

Now we get the string [“o”,” L “,” L “,”e”,”h”], continue to move the double pointer:

I and J meet, and the exchange is over. The result of the above exchange process [” O “,” L “,” L “,” E “,” H “] is the final answer we want.

To summarize

The overall steps are as follows:

  1. We set two Pointersi 和 jWhen initialized, williPointing to the string header,jPoint to the end of the string
  2. wheni < jWhen switchingi 与 jThe character pointed to completes the “inversion” required by the topic. Move the double pointer after the exchange: williIf I go 1 to the right,jWe move 1 to the left
  3. wheni >= j, end the loop and get the answer

The specific implementation

Python

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """ Do not return anything, modify s in-place instead. """
        length = len(s)
        i = 0
        j = length - 1
        while i < j:
            s[i], s[j] = s[j], s[i]
            i += 1
            j -= 1
Copy the code

Go

func reverseString(s []byte)  {
    i := 0
    j := len(s) - 1
    for i < j {
        s[i], s[j] = s[j], s[i]
        i += 1
        j -= 1}}Copy the code

PHP

class Solution {

    / * * *@param String[] $s
     * @return NULL
     */
    function reverseString(&$s) {
        $i = 0;
        $j = count($s) - 1;
        while($i < $j) { $tmp = $s[$i]; $s[$i] = $s[$j]; $s[$j] = $tmp; $i++; $j--; }}}Copy the code

The complexity of the

  • Time complexity:O(n)
  • Space complexity:O(1)

Review past

  • Diagram to select TOP interview questions 001 | LeetCode 237. Delete a node from a linked list
  • Diagram to select TOP interview questions 002 | LeetCode 104. The maximum depth of a binary tree

Recommended reading

  • Graphic double pointer | LeetCode 27. Remove elements
  • Get the interview series | partition algorithm by three steps

🐱

If you think the article is well written, please do me two small favors:

  1. Like and follow me to get this article seen by more people
  2. Pay attention to the public number “programming to save the world”, the public number focuses on programming foundation and server research and development, you will get the first time the new article push ~

Original is not easy, great encouragement ~ thank you!