[Leetcode]151. Reverse Words in a String

1. problem : 

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

 

 

 

2. solution 1 : 

class Solution:
    def reverseWords(self, s: str) -> str:
        s = s.split(" ")
        s  = [i for i in s if i]
        s.reverse()
    
        return " ".join(s)

split으로 s를 단어별로 구분하는 리스트를 만들고, 이 리스트에 빈값을 없애준다. 그다음, reverse 시켜서 , 단어의 위치를 역순으로 만들어준 다음. " ". join(s)를 이용해 list내의 단어들을 스페이스 간격이 있게 하여, return 한다. 

이 방법은 그냥 built-in method로 다 푼 것이기 때문에, 그렇게 좋다 할만한 요소가 없다.

 

3. solution 2 : 

class Solution:
    def reverseWords(self, s: str) -> str:
        stack = []
        word = [] 
        for char in s:
            if char != ' ':
                word.append(char) 
            else:
                if word:
                    stack.append(''.join(word)) 
                    word = []
        if word:
            stack.append(''.join(word))
        result = []
        while stack:
            result.append(stack.pop())
        return ' '.join(result)

 Stack이라는 자료구조를 이용하여 푼 방법이다. Stack은 LIFO이다. 즉, 마지막에 들어온 element가 제일 빨리 나간다는 특성이 있다. 따라서, string s를 loop로 돌리면서, word에 단어를 추가하고, 스페이스가 다시 나온다면 그 단어를 stack에 추가한다. 이때 ''. join()이라는 method를 이용해서, 따로 떨어져 있는 문자들을 다시 붙여준다. 마지막에 if word: 문이 하나 더 있는 것을 볼 수 있다. 이유는 만약에 tail 쪽에 space가 없었을 경우, word가 추가되지 않기 때문에 달아준 조건이다. 

마지막으로, stack에 담긴 word들을 이제 pop으로 (LIFO) 꺼내서, result에 더해준다. 

 

4. Solution 3 : 

class Solution(object):
    def reverseWords(self, s):
        length = len(s)
        word_positions = []  # To store start and end indices of words
        
        i = 0
        # Iterate through the string to identify word boundaries
        while i < length:
            # Skip leading spaces
            while i < length and s[i] == ' ':
                i += 1
            if i == length:
                break
            
            start = i  # Start of the word
            
            # Move to the end of the word
            while i < length and s[i] != ' ':
                i += 1
            end = i - 1  # End of the word
            
            # Store the start and end indices of the word
            word_positions.append((start, end))
        
        result = []
        # Reverse the order of the words and build the result string
        for start, end in reversed(word_positions):
            word = s[start:end + 1]
            result.append(word)
        
        return ' '.join(result)

이 풀이법은 space를 지나가면서 starting word가 나올 때까지 whilel문을 돌리고, starting word의 index를 표시해 둔다. 그다음 space가 나올 때까지 while loop를 돌려, end_index를 얻는다. 이때, i -1이 end _index인 이유는 space index에서 멈췄기 때문에, 그렇다. 그다음 start, end 튜플을 리스트에 더해주고, 이 index를 기준으로 word를 생성한 다음, return 한다.