[Leetcode/String Manipulation] 151. Reverse Words in a String

 

 

1️⃣번째 방법

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(s.split()[::-1])

시간 복잡도 및 공간 복잡도

• 시간 복잡도: O(n)
  • split() → O(n)
  • [::-1] (리스트 뒤집기) → O(n)
  • " ".join() → O(n)
  • 따라서 전체 시간 복잡도는 O(n) 입니다.
• 공간 복잡도: O(n)
  • split()이 새로운 리스트를 생성하므로 O(n)의 추가 공간이 필요합니다.

2️⃣번째 방법

Follow-up: O(1) 추가 공간으로 해결할 수 있을까?

문자열이 가변(mutable)한 경우, O(1) 공간에서 In-place 방식으로 해결할 수 있습니다.

파이썬에서는 문자열이 **불변(immutable)**이라서 직접 수정할 수 없지만, 리스트로 변환 후 처리하면 가능합니다.

📌 In-place 해결 방법

1. 문자열을 리스트로 변환 (s = list(s))
2. 전체 문자열을 뒤집음 (문자 단위)
3. 개별 단어를 다시 뒤집어서 원래 순서로 정렬
4. 공백 정리 (연속된 공백 제거, 단어 사이에는 하나의 공백만 유지)

class Solution:
    def reverseWords(self, s: str) -> str:
        # 1. 문자열을 리스트로 변환
        s = list(s)

        # 2. 문자열 전체 뒤집기
        self.reverse(s, 0, len(s) - 1)

        # 3. 단어 개별적으로 뒤집기
        self.reverse_each_word(s)

        # 4. 공백 정리
        return self.clean_spaces(s)

    def reverse(self, s, left, right):
        """리스트 s의 left부터 right까지 뒤집기"""
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

    def reverse_each_word(self, s):
        """각 단어를 뒤집음"""
        n = len(s)
        start = 0
        while start < n:
            while start < n and s[start] == ' ': # 공백 건너뛰기
                start += 1  
            end = start
            while end < n and s[end] != ' ': # 단어 찾기
                end += 1  
            self.reverse(s, start, end - 1)  # 단어 뒤집기
            start = end  # 다음 단어로 이동
            
    def clean_spaces(self, s):
        i = 0
        n = len(s)
        res = []
        
        while i < n:
            while i < n and s[i] == ' ':  # 공백 건너뛰기
                i += 1
            if i >= n:
                break
            start = i
            while i < n and s[i] != ' ':  # 단어 찾기
                i += 1
            res.append("".join(s[start:i]))  # 단어 추가
        
        return " ".join(res)  # 단어를 공백으로 연결

In-place 방법의 시간 복잡도 & 공간 복잡도

• 시간 복잡도: O(n)
  • 문자열 뒤집기 → O(n)
  • 단어 개별 뒤집기 → O(n)
  • 공백 정리 → O(n)
  • 총 O(n)
• 공간 복잡도: O(1) (추가적인 리스트 사용 없음)