[LeetCode] 344. Reverse String (문자열 뒤집기)

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

Do not allocate extra space for another array, you must do this by > modifying the input array in-place with O(1) extra memory.

다른 추가 공간을 사용하지 않고 문자열을 뒤집어야한다.

✍️ 풀이

---

• 다른 추가 공간을 사용하지 않기 위해선 문자열을 모두 뒤집고 반환하는 것이 아니라 뒤집을 위치와 문자를 찾은 후에 바로 문자를 교환해줘야한다.

1. 문자열의 시작과 끝을 정해 서로 교환해나가는 방법 (투 포인터)
2. 리스트 슬라이싱을 활용한 방법

🛠 코드

• 리스트를 원소를 앞-뒤로 검사하는 가장 기본적인 풀이방법이다.

---

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        가장 기본적인 앞-뒤 문자 교환
        """
        ln = len(s)
        for i in range(int(ln / 2)):
            tmp = s[i]
            s[i] = s[ln - 1 - i]
            s[ln - 1 - i] = tmp


    def reverseStringTwoPointer(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

✍️ 다른 사람 풀이

---

• 문자열 슬라이싱을 이용한 방법 (신기하게도 가장 빠르다..)

🛠 다른 사람 코드

---

    def reverseStringListComp(self, s: List[str]) -> None:
        s[:] = s[::-1] # 가장 빠름

📝 정리

---

• 간단한 투 포인터

🎈 참고

---

Book 링크