unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 151: Reverse Words in a String

link

Time: \mathcal{O}(n), space: O(n).

class Solution:
    def reverseWords(self, s: str) -> str:
        word_list = s.split()
        word_list_reversed = reversed( word_list )
        return " ".join( word_list_reversed )

We can do the reversing in-place:

  1. First pass: Copy the words to the beginning of s and remove extra spaces. Now the words are in s[0:n]
  2. Second pass: Reverse the entire string (s[0:n])
  3. Third pass: Restore each individual word by reversing

Since Python’s str is immutable, we first convert s to a List[str] and once reversing is done, return s[0:n] as a str.

Time: \mathcal{O}(n), space: \mathcal{O}(1).

class Solution:
    def reverse_part(self, s: List[str], begin: int, end: int) -> None:
        while begin < end:
            s[begin], s[end] = s[end], s[begin]
            begin += 1
            end -= 1

    # Copy the words to the beginning with just enough spaces
    def remove_extra_spaces(self, s: List[str]):
        n = len(s)

        begin = 0
        while begin < n and s[begin] == " ":
            begin += 1
        if begin == n:
            return 0

        end = n - 1
        while s[end] == " ":
            end -= 1

        i = -1
        while begin <= end:
            # Extra space, skip
            if s[begin] == " " and (i < 0 or s[i] == " "):
                begin += 1
                continue

            i += 1
            s[i] = s[begin]
            begin += 1

        return i + 1

    def reverseWords(self, s: str) -> str:
        s = list(s)

        n = self.remove_extra_spaces(s)
        if n == 0:
            return ""

        self.reverse_part(s, 0, n - 1)

        # Restore each word by reversing
        begin, end = 0, 0
        while end <= n:
            if end == n or s[end] == " ":
                self.reverse_part(s, begin, end - 1)
                begin = end + 1
            end += 1

        return "".join(s[0:n])

tanvirdotzaman

Leave a comment