[LeetCode] #344. Reverse String (python)

문제

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

Reverse String - LeetCode

주어진 문자열을 뒤집어야 하는데 리턴 없이 리스트 내부를 조작해야 하고 시간복잡도가 O(1)이어야 한다.

 

 

풀이

 

#책풀이

 

1. 파이썬 내장함수 reverse() 사용

 

처음에는 인덱싱을 쓰면 되는건줄 알았는데 계속 안되길래 모르겠어서 책을 보니까 s.reverse()를 사용하면 되는 간단한 문제였다.

책을 보니까 인덱싱을 쓴 것도 원래는 되어야 하는데 해당 문제에서는 공간복잡도 제한이 있어 처리가 되지 않는다고 한다.

인덱싱을 사용할 때 s[:]=s[::-1] 이렇게 하면 된다고 한다.

 

파이썬에는 reverse()와 reversed()가 있는데 reverse()는 리스트를 바로 뒤집는다. 

reversed는 뒤집어진 리스트를 반환한다.

사용방식도 다르다.

reverse() => s.reverse()

reversed() => reversed(s)

 

 

2. 투 포인터를 이용한 스왑

 

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

 

문장 처음과 끝부분에서 시작하는 포인터 left, right을 만든다.

left보다 right이 만나기 전까지 left, right 위치에 있는 문자열을 서로 바꿔주고 포인터는 계속 움직여준다.

left는 오른쪽으로 이동하고 right은 왼쪽으로 이동한다.

 

 

참고한 책 : 파이썬 알고리즘 인터뷰