GoCalf Calf 的自留地 · 昙花一现

344. Reverse String

Problem

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.

https://leetcode.cn/problems/reverse-string/

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:

Test Cases

python
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
solution_test.py下载完整源码
py
import pytest

from solution import Solution


@pytest.mark.parametrize('s, expected', [
    (["h","e","l","l","o"], ["o","l","l","e","h"]),
    (["H","a","n","n","a","h"], ["h","a","n","n","a","H"]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, s, expected):
    s = s.copy()
    sol.reverseString(s)
    assert s == expected

Thoughts

用两个指针分别指向数组的首尾,交换两个指针的字符,然后向中间移动指针,直到二者相遇。

时间复杂度 O(n),空间复杂度 O(1)。

Code

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

评论需要 JavaScript。