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
        }
    }
}

LeetCode Solution, Easy, 344. Reverse String

Comments

LeetCode Solution

More from this blog

如何開始入門軟體工程領域 - 名詞解釋（長期更新）

我的 MacBook Pro (Apple Silicon) 設定

ChatGPT 下的發展預想

一些覺得有用的工具蒐藏

LeetCode Solution, Medium, 607. Sales Person

344. Reverse String

題目敘述

題目翻譯

解法解析

解法範例

Go

JavaScript

Kotlin

PHP

Python

Rust

Swift

Command Palette

Comments

LeetCode Solution

More from this blog

344. Reverse String

題目敘述

題目翻譯

解法解析

解法範例

Go

JavaScript

Kotlin

PHP

Python

Rust

Swift