Reverse the order of words in a string

Posted: 20 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
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
Approach 1

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.
Try Problem