You are given a character array s
representing a sentence, where words are separated by single spaces. Your task is to reverse the order of words in the sentence. You must perform this reversal in-place, meaning you cannot allocate extra space for a new array. You are only allowed to modify the original character array.
For example:
Input: s = ['t', 'h', 'e', ' ', 's', 'k', 'y', ' ', 'i', 's', ' ', 'b', 'l', 'u', 'e']
Output: s = ['b', 'l', 'u', 'e', ' ', 'i', 's', ' ', 's', 'k', 'y', ' ', 't', 'h', 'e']
Input: s = ['h', 'e', 'l', 'l', 'o']
Output: s = ['h', 'e', 'l', 'l', 'o']
Input: s = ['a', ' ', 'b']
Output: s = ['b', ' ', 'a']
Constraints:
1 <= s.length <= 10^5
s[i]
is an English letter (uppercase or lowercase), digit, or space ' '.s
.s
are separated by a single space.Write a function that takes the character array s
as input and modifies it in-place to reverse the order of words.
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force method solves this by looking at every possible combination. Think of it like manually trying out different arrangements of the words in the string. We will reverse the entire string, then reverse each word individually.
Here's how the algorithm would work step-by-step:
def reverse_words(list_of_characters):
def reverse_substring(list_of_characters, start, end):
while start < end:
list_of_characters[start], list_of_characters[end] = list_of_characters[end], list_of_characters[start]
start += 1
end -= 1
# Reverse the entire string to put words in reverse order
reverse_substring(list_of_characters, 0, len(list_of_characters) - 1)
start_index = 0
for index in range(len(list_of_characters) + 1):
if index == len(list_of_characters) or list_of_characters[index] == ' ':
# Reverse each word to get letters in correct order
reverse_substring(list_of_characters, start_index, index - 1)
start_index = index + 1
The trick to reversing words in place is to first reverse the entire string. After that, reverse each word individually. This approach avoids needing extra memory to store the reversed string or individual words.
Here's how the algorithm would work step-by-step:
def reverse_words(list_of_characters):
def reverse_range(list_to_reverse, start_index, end_index):
while start_index < end_index:
list_to_reverse[start_index], list_to_reverse[end_index] = list_to_reverse[end_index], list_to_reverse[start_index]
start_index += 1
end_index -= 1
# First, reverse the entire string.
reverse_range(list_of_characters, 0, len(list_of_characters) - 1)
start_of_word_index = 0
for index in range(len(list_of_characters) + 1):
# Identify word boundaries using spaces
if index == len(list_of_characters) or list_of_characters[index] == ' ':
# Reverse each word individually.
reverse_range(list_of_characters, start_of_word_index, index - 1)
# Move the start index to the next word.
start_of_word_index = index + 1
Case | How to Handle |
---|---|
Null or empty input string | Return immediately or throw an IllegalArgumentException as appropriate for the language. |
String with only spaces | Treat multiple spaces as single spaces, resulting in an empty or single-space string after reversal. |
String with leading/trailing spaces | Trim leading and trailing spaces before reversing the words to avoid extra spaces in the output. |
Single word string | The reversed string will be the same as the original string, so return the original. |
String with consecutive multiple spaces between words | Reduce multiple spaces to single spaces during processing. |
Maximum length string (memory constraints) | Ensure the solution doesn't exceed memory limits and potentially consider in-place reversal if memory is a concern. |
String containing non-ASCII characters | Ensure the string reversal algorithm handles Unicode characters correctly, using UTF-8 encoding or similar. |
Integer overflow when calculating lengths or indices | Use appropriate data types (e.g., long) or validate input lengths to prevent integer overflow. |