LeetCode - 151. Reverse Words in a String (python)

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

• 난이도 : medium
• 알고리즘 : string

접근방법

• 문제 자체는 다양한 방법으로 해결될 수 있을 것 같아서 시간복잡도와 공간복잡도를 최대한 줄이는 방법을 생각해 보았다
• start_idx와 end_idx를 두어 answer에 단어를 추가하며 답을 구한다
• 전처리의 편의를 위해 s의 앞에 공백을 하나 추가한다
• 위와 같은 방법으로 O(n)의 시간 복잡도와 O(n)의 공간복잡도 내에서 문제를 해결

소스코드

class Solution:
    def reverseWords(self, s: str) -> str:
        s = ' ' + s
        answer = ""
        n = len(s)
        if n == 1:
            return s[0]
        
        end_idx = n - 1
        while end_idx > 0 and s[end_idx] == ' ':
            end_idx -= 1
        start_idx = end_idx - 1

        while start_idx >= 0:
            if s[start_idx] == ' ':
                answer += (s[start_idx + 1:end_idx + 1] + ' ')
                end_idx = start_idx
                while end_idx > 0 and s[end_idx] == ' ':
                    end_idx -= 1

                start_idx = end_idx

            start_idx -= 1
        
        return answer[:len(answer) - 1]

시간복잡도 & 공간복잡도