344. Reverse String

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 609

種類 : array, string
難度 : easy
題目 : 344. Reverse String

思維邏輯

  • 使用list的reverse()
  • 前後元素對調

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # s.reverse()

        for i in range(int(len(s)/2)): # len(s) // 2
            temp = s[i]
            s[i] = s[-1*(i+1)]
            s[-1*(i+1)] = temp

            # 不使用多於變數
            # s[i], s[n - i - 1] = s[n - i - 1], s[i]

時間複雜度: O(n/2)
空間複雜度: O(1)

難點

無

最佳解法

1
2
3
4
5
6
7
8
9
10
"""
雙指針
"""
class Solution:
    def reverseString(self, s: List[str]) -> None:
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

時間複雜度: O(n/2)
空間複雜度: O(1)