[2024] day 155. leetcode 344. Reverse String

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 6월 2일 (일)
Leetcode daily problem

344. Reverse String

https://leetcode.com/problems/reverse-string/?envType=daily-question&envId=2024-06-02

Problem

문자열을 반전시키는 함수를 작성한다. 입력 문자열은 문자 배열로 제공된다. O(1) 추가 메모리를 사용하여 입력 배열을 내부에서 수정하여 이를 수행해야 한다.

Solution

two pointer

정렬을 사용하게 되면 추가 배열 O(n)을 사용하고, 슬라이싱해서 역전시켜도 O(n)을 사용하게 된다.
O(1)의 메모리를 사용하면서 문자열을 반전시키기 위해서는 two pointer를 사용해서 문자열의 가장 왼쪽, 가장 오른쪽을 포인터로 두고 서로 swap 해가면서 왼쪽은 오른쪽으로 이동 오른쪽은 왼쪽으로 이동하는 식으로 문자열을 교환한다.

Code

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

Complexicity

시간 복잡도

왼쪽에서 오른쪽으로 이동하는 포인터 l, 오른쪽에서 왼쪽으로 이동하는 포인터 r을 업데이트 하는 반복은 문자열 길이 n에서 n/2번 실행되므로, 전체 시간 복잡도는 O(n) 이다.

공간 복잡도

업데이트 되는 포인터의 상수 크기의 공간만 사용되므로 공간복잡도는 O(1)로, 추가적인 데이터 구조를 사용하지 않는다.
전체 공간 복잡도는 O(1) 이다.