리트코드 - 151. Reverse Words in a String

https://leetcode.com/problems/reverse-words-in-a-string/description/?envType=study-plan-v2&envId=leetcode-75

Reverse Words in a String - LeetCode

입력 문자열 s가 주어지면 단어의 순서를 반대로 합니다. s의 단어는 하나 이상의 공백으로 구분된다. 이때 하나의 공백으로 연결된 역순의 단어 문자열을 반환한다.

이때, s에는 선행 또는 후행 공백이 포함되거나 두 단어 사이에 여러 개의 공백이 포함될 수 있지만, 반환되는 문자열에는 단어를 구분하는 공백이 하나만 있어야 한다.

 

follow - up: 사용 중인 언어에서 문자열 데이터 유형이 변경 가능한 경우 O(1)의 추가 공간으로 제자리에서 해결할 수 있나요?

 

파이썬에서 문자열이 불변이라는 제약을 무시하고, 문자열을 가변적인 리스트로 취급할 수 있다고 가정하면, 이 문제는 O(1)의 공간 복잡도로 해결할 수 있다. 이를 위해서는 문자열을 리스트로 변환한 후, 투 포인터 기법을 사용하여 단어 단위로 리스트 내에서 직접 문자들의 위치를 바꾸는 방식을 사용할 수 있다.

 

1. 문자열을 리스트로 변환합니다. (이 단계의 공간 복잡도는 무시.)
2. 문자열 내에서 단어 단위로 뒤집는다. 이를 위해 각 단어의 시작과 끝을 찾은 후, 해당 범위 내에서 문자들의 위치를 서로 바꾼다.
3. 전체 문자열을 뒤집어서, 모든 단어가 올바른 순서로 배열되도록 한다.
4. 결과 리스트를 다시 문자열로 변환한다.

class Solution:
    def reverse(self, s: list, start, end):
        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

    def reverseWords(self, s: str) -> str:
        s = list(s)
        start = 0
        for i in range(len(s)):  # O(n)
            if s[i] == " ":
                self.reverse(s, start, i - 1)  # O(k) k는 해당 단어의 길이
                start = i + 1
        self.reverse(s, start, i)  # O(m) m은 해당 단어의 길이
        self.reverse(s, 0, len(s) - 1)  # O(n)

        return " ".join("".join(s).split())  # O(n)

 

처음에 s = list(s)를 통해 리스트를 변환하면  ['a', ' ', 'g', 'o', 'o', 'd', ' ', ' ', ' ', 'e', 'x', 'a', 'm', 'p', 'l', 'e']와 같다.

이를 단어 단위로 뒤집으면['a', ' ', 'd', 'o', 'o', 'g', ' ', ' ', ' ', 'e', 'l', 'p', 'm', 'a', 'x', 'e']가 된다.

이를 다시 역으로 바꾸면 ['e', 'x', 'a', 'm', 'p', 'l', 'e', ' ', ' ', ' ', 'g', 'o', 'o', 'd', ' ', 'a']가 된다.

이를 공백을 제외하고 단어별고 구분한 다음, 이 단어들을 단일 공백으로 다시 결합하면 된다.