Reverse Words in a String II

Easy
0/40
Average time to solve is 10m
19 upvotes
Asked in companies
UberPharmEasyHCL Technologies

Problem statement

You are given a string ‘STR’ containing space-separated words. A word is a sequence of non-space characters. Your task is to reverse the order of words in ‘STR’.

Note: Try to do it in-place without allocating extra space.

Example: 
‘STR’ = “when in doubt use brute force”
The reverse order of words in ‘STR’ is: “force brute use doubt in when”.
Note: 
1. ‘STR’ does not contain any leading or trailing spaces.
2. The words are always separated by a single whitespace character.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line and only line of each test case contain a single string ‘STR’.
Output format: 
For every test case, return a string with the reverse orders of words as ‘STR’.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 100
1 <= Length of ‘STR’ <= 10^3
The string ‘STR’ contains only ‘a-z’ and whitespace characters.

Time limit: 1 second

Sample input 1:

2
when all else fails reboot
java is to javascript what a car is to carpet

Sample output 1:

reboot fails else all when
carpet to is car a what javascript to is java

Explanation of sample input 1:

Test Case 1:
‘STR’ = “when all else fails reboot”
The reverse order of words in ‘STR’ is: “reboot fails else all when”.

Test Case 2:
‘STR’ = “java is to javascript what a car is to carpet”
The reverse order of words in ‘STR’ is: “carpet to is car a what javascript to is java”.

Sample input 2:

2
no code has zero defects
whitespace is never white

Sample output 2:

defects zero has code no
white never is whitespace
Hint

Try to convert ‘STR’ into an array of words

Approaches (2)
Convert to an array of words

Use an array ‘ARR’ to store the words in ‘STR’. Traverse the string ‘STR’ and append each word at the end of ‘ARR’. Use the string ‘RES’ to store the answer. Traverse the array ‘ARR’ in reverse and append the words in ‘ARR’ to ‘RES’ followed by a whitespace character.

 

  • Create an empty array of string ‘ARR’.
  • Initialize an empty string ‘CUR_STR’. Use it to store a single word from ‘STR’.
  • Run a loop where ‘i’ ranges from 0 to ‘LENGTH(STR) - 1’:
    • If ‘STR[i]’ is not equal to space, then:
      • ‘CUR_STR.APPEND(STR[i])’. Add the characters in ‘STR’ to ‘CUR_STR’ until we encounter a space.
    • Else:
      • ‘ARR.APPEND(CUR_STR)’. As ‘STR[i]’ is a space, ‘CUR_STR’ stores a word, so append ‘CUR_STR’ at the end of ‘ARR’.
      • Set ‘CUR_STR’ to an empty string. So it can store the next word of ‘STR’.
  • ‘ARR.APPEND(CUR_STR)’. A whitespace character does not follow the last word.
  • Initialize an empty string ‘RES’ to store the answer.
  • Run a loop where ‘i’ ranges from ‘LENGTH(ARR) - 1’ to ‘1’:
    • ‘RES.APPEND(ARR[i])’
    • ‘RES.APPEND( )’. Add a whitespace character between words.
  • ‘RES.APPEND(ARR[0])’. Add the last word separately as a whitespace character does not follow it.
  • Return ‘RES’ as the answer.
Time Complexity

O(LEN), where ‘LEN’ is the length of string ‘STR’.

 

We traverse the string ‘STR’ once to create the array ‘ARR’ in ‘O(LEN)’ time. Similarly, creating the string ‘RES’ from the array ‘ARR’ requires ‘O(LEN)’ time.

Space Complexity

O(LEN), where ‘LEN’ is the length of string ‘STR’.

 

We store the words of the string ‘STR’ in array ‘ARR’ and the reverse order of the words in ‘STR’ in ‘RES’, both requiring ‘O(LEN)’ space.

Code Solution
(100% EXP penalty)
Reverse Words in a String II
Full screen
Console