[LeetCode] 344. Reverse String

344. Reverse String

Easy

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

 

Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

 

Constraints:

• 1 <= s.length <= 105
• s[i] is a printable ascii character.

 

---

문제 풀이

• 주어진 문자열 리스트를 반대로 뒤집는 문제이다. 
• 제한사항을 보면 문자열의 최대길이가 10^5이기 때문에 최대 O(N) 풀이법으로 문제를 풀어야한다.
• 배열안의 값들을 각각 접근하기 쉬운 방법은 투 포인터이다.
• 포인터들을 두개 생성한다, 하나는 맨앞이며 하나는 맨뒤를 가르키는 인덱스로 초기화한다.
• 물론 브루트 포스로 각각의 글자들을 옮기는 방법도 있겠으나, 문제 내에서 O(1) Constant(상수) 메모리 복잡도 내에 풀어야한다.
• 그래서 두개씩 앞뒤 글자를 교체 Swap 을 해준다. 
• while 문에서는 두개의 포인터가 같거나 시작 포인터와 끝 포인터의 값의 크기가 뒤바뀐다면 종료하도록 만들었다.
• while 문의 조건을 작성할 때에는 언제까지 True 조건이어야하는지 신경써서 참의 조건을 적어주면 된다.
• 만일 조건을 생성하기 어렵다면, 배열의 포인터들을 직접 손으로 그려서 어떤 부분에서, 조건에서 끝내야하는지 확인해보자.

소스 코드

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