Given a character array s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by a single space.
Your code must solve the problem in-place, i.e. without allocating extra space.
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 <= 10^5s[i] is an English letter (uppercase or lowercase), digit, or space ' '.s.s does not contain leading or trailing spaces.s are guaranteed to be separated by a single space.
The description was taken from https://leetcode.com/problems/reverse-words-in-a-string-ii/.
#O(N) Time, O(1) Space
class Solution:
def reverseWords(self, s: List[str]) -> None:
def reverse(left:int, right:int) -> None:
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
reverse(0, len(s)-1)
left, right = 0, 0
while right < len(s):
if s[right] == " ":
reverse(left, right-1)
left = right + 1
elif right == len(s) - 1:
reverse(left, right)
right += 1Without any additional space, we are very limited to what we can do. We'll need to throw out any stack or array solutions that we may have previously considered.
If we need to reverse a list using constant space, without any built-in methods, we can achieve that by utilizing two pointers to continuously swap the outer two elements before they overlap.
Let's just take the first example and see what happens when we do that:
["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Turns to:
["e", "u", "l", "b", ' ', "s", "i', ' ', "y", "k", "s", ' ', "e", "h", "t"]
We can see that the order of the words is correct, but the words themselves are reversed.
Why don't we traverse the string once more and just reverse each word then?
["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
The entire string will be reversed, then each word will be reversed, so we will be able to achieve this result in three visits through each word.
Let's start by creating our reverse function.
The function will take a left and a right pointer.
def reverse(left:int, right:int) -> None:
While the two pointers haven't overlapped, we will continue swapping the elements at these pointers then moving the pointers inward.
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
Next, we will reverse the entire list using this helper function.
reverse(0, len(s)-1)
Afterward, we will initialize a left and a right pointer at the first index of the array.
left, right = 0, 0
While the right pointer hasn't reached the end of the list, we'll need to keep reversing.
while right < len(s):
If the right pointer hits a space, we'll need to reverse the word within the range of the left pointer up to that space, excluding it from the reversal.
Once we do that, we will move our left pointer past the space, onto the first character of the next word.
if s[right] == " ":
reverse(left, right-1)
left = right + 1
However, there is no space at the end of the array so if our right pointer is at the last character of the list, we will reverse the word within the range of our left and right pointer.
There's no point moving the left pointer here because there will be nothing else to reverse after this word.
elif right == len(s) - 1:
reverse(left, right)
Once we have finished with our reversal or haven't hit a space yet, we will increment the right pointer and continue trying to find the end of the current word.
right += 1