344. Reverse String

題目敘述

Write a function that reverses a string. The input string is given as an array of characters s`.

You must do this by modifying the input array in-place with O(1) extra memory.

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"]

Constraints:

• 1 <= s.length <= 10**5
• s[i] is a printable ascii character.

Hint 1:

The entire logic for reversing a string is based on using the opposite directional two-pointer approach!

題目翻譯

有一個包含字母的陣列 s ，需要將其反轉順序。是否可以用原地演算法將其空間複雜度只有在 O(1) 呢？

解法解析

雖然有些語言有更簡便的語法糖可以使用，不過既然是練 LeetCode 我們就先略過吧。主要的解法就是使用 Two point 同時取對應的左右兩側的 index 然後將其值互換。有兩種做法，一種是取最左右兩側的 index 然後往中心點收斂。另一種就是從中心點往外擴展到邊界。

解法範例

Go

func reverseString(s []byte) {
    left := 0
    right := len(s) - 1
    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}

JavaScript

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
    let left = 0,
        right = s.length - 1;
    while (left < right) {
        [s[left], s[right]] = [s[right], s[left]];
        left++;
        right--;
    }
};

Kotlin

class Solution {
    fun reverseString(s: CharArray): Unit {
        val n = s.size

        for (i in 0..(n / 2 - 1)) {
            val temp = s[i]
            s[i] = s[n - 1 - i]
            s[n - 1 - i] = temp
        }
    }
}

PHP

class Solution
{

    /**
     * @param String[] $s
     * @return NULL
     */
    function reverseString(&$s)
    {
        $left = 0;
        $right = count($s) - 1;
        while ($left < $right) {
            $temp = $s[$left];
            $s[$left] = $s[$right];
            $s[$right] = $temp;
            $left++;
            $right--;
        }
    }
}

Python

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

Rust

impl Solution {
    pub fn reverse_string(s: &mut Vec<char>) {
        let mut left = 0;
        let mut right = s.len() - 1;
        while left < right {
            s.swap(left, right);
            left += 1;
            right -= 1;
        }
    }
}

Swift

class Solution {
    func reverseString(_ s: inout [Character]) {
        let middel = Int(s.count / 2)
        for i in 0..<middel {
            let temp = s[i]
            s[i] = s[s.count - 1 - i]
            s[s.count - 1 - i] = temp
        }
    }
}