Day-15 Reverse words in a string

Background

This problem statement is a part of LeetCode's card Arrays and Strings. Under the sub-heading Conclusion.

Problem Statement

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

Example 1

Input: "the sky is blue"
Output: "blue is sky the"

Example 2

Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3

Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

1. A word is defined as a sequence of non-space characters.
2. Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
3. You need to reduce multiple spaces between two words to a single space in the reversed string.

Solution Approach 1

1. Replace double space with single space.
2. Remove leading and trailing spaces.
3. Reverse.

class Solution:
    def reverseWords(self, s: str) -> str:
        s.replace("  ", " ").rstrip().lstrip()
        string = s.split()
        string.reverse()
        return ' '.join(string)

Learnings and takeaways from the above snippet

1. We have hardcoded 2 spaces. Hardcoding in programming should never be done.
2. If count of consecutive spaces is increased. The code would fail.
3. Using built-in method reverse() could appear as a shortcut.

Updated solution overcoming the shortcomings listed above.

1. s.lstrip().rstrip().split(). Takes care of multiple spaces, leading spaces, trailing space.
2. replace reverse() with implementation of reverse.

class Solution:
    def reverseWords(self, s: str) -> str:
        string = s.lstrip().rstrip().split()
        start = 0
        end = len(string) - 1
        while start < end:
            temp = string[start]
            string[start] = string[end]
            string[end] = temp
            start += 1
            end -= 1

        return ' '.join(string)

Ps:
Last section of the post. Which starts from learnings from the shortcomings of the above snippet is updated after seeing the first comment.

Comments

[Rishiraj Purohit]

while the question says there can be multiple spaces and your solution only takes care of double spaces, second when there are questions like these the person asking the question expects the implementation and not the function so using string.reverse() is bit of a shortcut.

I would try to implement a queue and a stack and read the string from right to left, emptying the stack when hitting space and making sure I handle the case when I've already emptied the stack.

So during multiple space, first space will empty the stack, second will check that stack is empty so will simply move on. This approach may also handle trailing and leading space.

One special case would be the end of string where we empty the stack once again and have the result.

[Mridu Bhatnagar]

There can be multiple ways to solve a given problem.

I have updated the code. And, now all edge cases are being taken care of. Leading spaces, trailing spaces, multiple spaces. Built-in method reverse() is replaced by implementation of reverse().

[Jayaram K]

Hi
I tried to execute this script but it is not giving as expected result. Am i missing something?
t1=Solution()
print(t1.reverseWords('god'))
god

[Mridu Bhatnagar]

The test doesn't seem to be valid to me. Explaining below the reason.

The problem statement says - "Given an input string, reverse the string word by word." For them, string means "multiple words separated by space". Now, see the NOTE section. It says "A word is defined as a sequence of non-space characters."

The intent of the problem is to reverse each word present in the string. And the string contains multiple words. Here, you are testing it on only single word "god".

Correct input would be
Input - "god is kind"
Output - "kind is god"

Also, you would observe we are not reversing characters present in word. We are reversing the complete string.

I hope I have made it clear.

[Jayaram K]

Thanks for the clarification.After I converted the string into list,I was able to reverse it.Any suggestions for good books/links to start Datastructures& A for beginners?