151_Reverse Words in a String

[medium]

Given an input string, reverse the string word by word.

Note: need to make sure that the string only contains letters and spaces.

Test case 1 (easy)

Input: "the weather is good"
Output: "good is weather the"

Test case 2 (with spaces at the beginning and the end)

Input: "   the weather is good   "
Output: "good is weather the"

Test case 3 (only spaces in the string)

Input: "      "
Output: ""

Test case 4 (empty string)

Input: ""
Output: ""

Test case 5 (more than one space between words)

Input: "the    weather    is     good"
Output: "good is weather the"

Idea 1

• extract all words in to a list

• reverse the list

• join strings in the list with space

Complexity 1

• Time: $O(n)$
• Space: $O(n)$

Solution 1_v1 (with build-in functions split(), reverse(), join())

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """

        out = " ".join(reversed(s.split()))
        return out

Solution 1_v2 (write split(), use build in reverse(), join())

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """

        out = []        
        word = ""

        # split the string into a list of words
        for i in range(len(s)) :
            # if current character is not space, add it to word
            # if current character is space，and word is not empty, 
            # append current word to out and set word to empty
            # otherwise, continue with next character
            if s[i] != " " :
                word += s[i]
            elif word != "" :
                out.append(word)
                word = ""
            else :
                continue

        # if sting is not empty and last character is not space,
        # add current word to out
        if len(s) > 0 and s[-1] != " " :
            out.append(word)

        # reverse the list, then join with space
        return " ".join(reversed(out))

Idea 2

• reverse the entire string

• loop over the string, reverse the words, append space after each word, and neglect all the spaces.

Complexity 2

• Time: $O(n)$
• Space: $O(n)$

Solution 2

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """

        # current word
        word = ""
        # output reversed string
        out = ""

        # reverse input string
        s = s[ : :-1]

        for i in range(len(s)) :
            # For first letter in words except the first word, 
            # put the current stored word into out, let current word be the current letter.
            if s[i] != " " and s[i-1] == " " and word != "":
                out += word + " "
                word = s[i] 
            # For all other letters, update current word in a reversed order.
            elif s[i] != " " :
                word = s[i] + word
            # Skip all the spaces.
            else :
                continue
        # store the last word
        out += word
        return out

Idea 3

• reverse the entire string

• loop over the string, reverse the words, append space after each word, and neglect all the spaces.

• do everything in-place

Complexity 3

• Time: $O(n)$
• Space: $O(1)$

def reverseWords(s):
    """
    :type s: str
    :rtype: str
    """
    if s == "": return s
    s = list(s)

    # reverse the input string first
    s.reverse()

    # reverse each word
    start, end = 0, 0
    while end < len(s):
        if not s[end] == " ":
            end += 1
        elif start < end:
            # just finish one word
            s[start:end] = reversed(s[start:end])
            end += 1
            start = end
        elif start == end:  
            # the string starts with space or
            # there are multiple spaces between words
            s.pop(end)
    if start < end:
        # the last word is not reversed yet
        s[start:end] = reversed(s[start:end])
    if len(s) >= 1 and s[-1] == " ":
        # the string ends with space
        s.pop()
    return "".join(s)