Last Updated: 20 Mar, 2021
Reverse Words in a String II
Easy
Asked in companies
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
Approaches
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’.
- If ‘STR[i]’ is not equal to space, then:
- ‘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.
Reverse the string ‘STR’, so the new string ‘STR’ has the reverse order of words as that of the original string, but the characters in each word are also in reverse order compared to the original string. Now, reverse each word of the new string ‘STR’.
For example:
‘STR’ = “this is a string”
After taking reverse,
‘STR’ = “gnirts a si siht”
Now, take the reverse of each word in ‘str’ to get the answer,
‘STR’ = “string a is this”
Write a function ‘REVERSE_STRING()’ that reverses the string ‘RES’ from position ‘START’ to ‘END’.
‘REVERSE_STRING(string RES, integer START, integer END)’:
- Run a loop while ‘START’ is less than ‘END’. In each iteration, swap the characters of ‘res’ at position ‘START’ and ‘END’:
- ‘TEMP = RES[START]’
- ‘RES[START] = RES[END]’
- ‘RES[END] = TEMP’
- ‘START' += 1’
- ‘END' -= 1’
Call the function ‘REVERSE_STRING()’ with ‘STR’ as a parameter to reverse the string ‘STR’. After that, call this function for each word of ‘STR’.
- ‘REVERSE_STRING(STR, 0, LENGTH(STR) - 1)’. To take the reverse of ‘STR’.
- Initialize an integer ‘START' = 0. Use them to store the start position of each word in ‘STR’.
- Run a loop where ‘i’ ranges from 0 to ‘LENGTH(STR) - 1’:
- If ‘STR[i]’ is equal to space, then we have traversed the current word and call ‘REVERSE_STRING’ to reverse the word:
- ‘REVERSE_STRING(STR, START, i - 1)’.
- ‘START = i + 1’. Now ‘START’ points to the beginning of the next word.
- ‘REVERSE_STRING(STR, START, LENGTH(STR) - 1)’. A whitespace character does not follow the last word, so we need to reverse it separately.
- If ‘STR[i]’ is equal to space, then we have traversed the current word and call ‘REVERSE_STRING’ to reverse the word:
- Return ‘STR’ as the answer.