[LeetCode] 344. Reverse String 문제풀이 (+파이썬 코드)

문제 : 344. Reverse String

 

문자열을 뒤집는 문제이다. 단 in-place 방식으로 구현해야 한다.

면접에서 물어볼 거라 생각 못 한 질문! 풀이법이 간단해서 코테에는 잘 안 나오지만, 잘 알아두면 좋은 것 같다.

 

---

풀이

 

sol 1) 투 포인터를 이용한 swap

 

리턴 없이 리스트 내부를 직접 조작하는 방식이어서 space complexity는 O(1)

time complexity는 O(n)

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 += 1
            right -= 1
        
        return s

 

sol 1) 투 포인터를 이용한 swap
time complexity	O(1)
space complexity	O(N)