
Problem Statement
The problem presents an array of characters, s
, and the task is to reverse the sequence of words in-place. Here, a word is defined as a continuous sequence of non-space characters, and these words are distinguished from one another by a single space character within the array. It's crucial to achieve the word reversal without using extra space, meaning the solution must modify the array s
directly.
Examples
Example 1
Input:
s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output:
["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
Example 2
Input:
s = ["a"]
Output:
["a"]
Constraints
1 <= s.length <= 105
s[i]
is an English letter (uppercase or lowercase), digit, or space' '
.- There is at least one word in
s
. s
does not contain leading or trailing spaces.- All the words in
s
are guaranteed to be separated by a single space.
Approach and Intuition
The core concept for solving this task is to think about the problem in two key steps:
Reverse the entire array: This is the preliminary step where we reverse all characters in the array. This operation positions the words in the approximate desired order but reverses the individual words as well. For instance, reversing
["t","h","e"," ","s","k","y"]
entirely would yield["y","k","s"," ","e","h","t"]
.Reverse each word individually: After the entire array has been reversed, each word within will also be reversed. The second step is to correct this by reversing each word in its place. This process restores the correct orientation of characters within each word but retains the overall reversed word order.
Things to consider based on constraints:
- Since the operation must be performed in-place, techniques like array slicing or using additional arrays for storage are not allowed. Instead, operations will involve swapping elements directly within the input array.
- Special cases include arrays with only one word and where the first or last characters in the array are space characters. The function should be designed with these in mind, but the constraint assures no leading or trailing spaces, simplifying the operation somewhat.
- The algorithm needs to handle arrays up to the length of 105, emphasizing the need for an efficient solution, ideally linear in time complexity relative to the number of characters in the array.
This approach ensures that the solution adheres to the in-place requirement effectively by only modifying the array via element swapping and sequential traversals, aiming for a time complexity that is linear, i.e., O(n), where n is the number of characters in the array.
Solutions
- C++
class Solution {
public:
void reverseStringWords(vector<char>& strVec) {
reverse(strVec.begin(), strVec.end());
int wordStart = 0, wordEnd = 0;
int length = strVec.size();
while (wordStart < length) {
while (wordEnd < length && strVec[wordEnd] != ' ') {
wordEnd++;
}
reverse(strVec.begin() + wordStart, strVec.begin() + wordEnd);
wordEnd++;
wordStart = wordEnd;
}
}
};
This solution, aimed at the problem of reversing the words in a string using C++, employs an efficient approach to manipulate string data directly in place for enhanced performance and reduced memory usage.
The solution involves the following steps:
- Reverse the entire string initially to invert the order of characters.
- Iterate over the reversed string to identify individual words separated by spaces.
- Reverse each word found to restore its correct order while keeping the overall reversed word order intact.
Key details of the implementation:
- Utilize the
reverse
function from the C++ Standard Library for in-place string manipulation. - Identify the start and end of each word using a loop, and apply the
reverse
function to each word independently.
By reversing the entire string first and then each word, the solution achieves the goal of reversing the order of words in the string while maintaining the order of characters within each word. This method avoids the need for additional storage, thus being memory efficient.
- Java
class Solution {
public void reverseSegment(char[] s, int startIdx, int endIdx) {
while (startIdx < endIdx) {
char temporary = s[startIdx];
s[startIdx++] = s[endIdx];
s[endIdx--] = temporary;
}
}
public void reverseEachWordInArray(char[] s) {
int length = s.length;
int startPos = 0, endPos = 0;
while (startPos < length) {
// find end of the current word
while (endPos < length && s[endPos] != ' ') ++endPos;
// reverse current word
reverseSegment(s, startPos, endPos - 1);
// adjust to the start of next word
startPos = endPos + 1;
++endPos;
}
}
public void reverseWordsInSentence(char[] s) {
// reverse the entire character array
reverseSegment(s, 0, s.length - 1);
// then reverse each word in the array
reverseEachWordInArray(s);
}
}
This Java solution for reversing the words in a string in-place efficiently manipulates character arrays. Follow these key steps to understand the approach:
Define a helper method
reverseSegment
to reverse a segment within a character array between two indices. This method swaps characters from start to end until the entire segment is reversed.Implement
reverseEachWordInArray
to handle the reversal of each word individually:- Loop through the character array to identify individual words. Words are segments that end with a space character.
- Apply the
reverseSegment
method to each word identified.
The main method
reverseWordsInSentence
performs the overall task in two major steps:- First, reverse the entire character array to invert the order of all characters, effectively placing all words in their final reversed position in the array.
- Then, use
reverseEachWordInArray
to correct the order of characters within each word in the array.
This approach ensures that words are reversed in their position without any additional memory for storage, making the operation space-efficient.
- Python
class Solution:
def reverse_segment(self, arr: List[str], start: int, end: int) -> None:
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
def reverse_word_by_word(self, arr: List[str]) -> None:
length = len(arr)
begin = finish = 0
while begin < length:
while finish < length and arr[finish] != ' ':
finish += 1
self.reverse_segment(arr, begin, finish - 1)
begin = finish + 1
finish += 1
def reverseWords(self, s: List[str]) -> None:
self.reverse_segment(s, 0, len(s) - 1)
self.reverse_word_by_word(s)
The provided Python solution focuses on reversing the words in a given list of characters, effectively solving the "Reverse Words in a String II" problem without returning any value, as it modifies the list in place. This operation is done by defining and utilizing two main helper functions: reverse_segment
and reverse_word_by_word
.
Here's how the code achieves its goal:
Initial Full Reverse: *Applies the
reverse_segment
function initially to the entire string. This action reverses the whole array of characters. For example, given "the sky is blue", it transforms the list to "eulb si yks eht".Word-by-Word Reverse:
- Executes the
reverse_word_by_word
method, which then processes each word individually. It scans for word boundaries (spaces) and appliesreverse_segment
to each word segment to restore the original word order while keeping the individual words reversed.
- Executes the
Here's what happens during the execution:
- reverse_segment: Takes a segment of the array defined by start and end indices, and reverses the characters within that segment in place using a while loop.
- reverse_word_by_word: Iterates through the complete list of characters. For each word detected (delimited by spaces), it applies
reverse_segment
to reverse back each word in its place. - reverseWords: Combines these functions methodically. It reverses the whole character list first to achieve the reversed word order. Then, it reverses each word to correct the orientation of the characters within words.
This method is both time-efficient and space-efficient as it optimizes in-place operations without utilizing additional memory for another array, fitting well within typical constraints for string manipulation challenges.
No comments yet.