Leetcode - Reverse Words in a String II (Java)
Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters. The input string does not contain leading or trailing spaces and the words are always separated by a single space. For example, Given s = "the sky is blue", return "blue is sky the". Could you do it in-place without allocating extra space?
Analysis
This problem is similar to the rotate array to right by k steps problem.
There are two steps:
- use the space ‘ ‘ to determine the boundary of words. We reverse each subarray separated by space.
2. reverse the whole array.
See the following implementation in Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class ReverseWords { public void reverseWords(char[] str) { int left = 0; for(int right=0; right < str.length; right++){ if(str[right] == ' '){ reverse(str, left, right-1); left = right + 1; } } reverse(str, left, str.length-1); reverse(str, 0, str.length-1); } public void reverse(char[] str, int left, int right){ while(left < right){ char temp = str[right]; str[right] = str[left]; str[left] = temp; left++; right--; } } } |
