Problem
Given a string s containing words separated by spaces, return the string with the order of the words reversed.The result should contain only a single space between consecutive words, with no leading or trailing spaces.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "the sky is blue"Output
"blue is sky the"Solution
This solution uses a Two Pointer approach while scanning the string from right to left. The pointeri searches for the beginning of each word, while j marks the end of that word. First, we skip any spaces from the end of the current search range. We then move
i backward until a space or the beginning of the string is reached. The characters between i + 1 and j form the current word.
We append each discovered word to the result. Since we process the words from right to left, they are automatically added in reverse order. A single space is added between words.
class Solution {
public String reverseWords(String s) {
int n = s.length();
StringBuilder sb = new StringBuilder();
int i = n - 1, j = n - 1;
while (i >= 0) {
while (i >= 0 && s.charAt(i) == ' ') {
i--;
j--;
}
if (i < 0)
break;
while (i >= 0 && s.charAt(i) != ' ')
i--;
if (!sb.isEmpty())
sb.append(" ");
sb.append(s.substring(i + 1, j + 1));
j = i;
}
return sb.toString();
}
}Complexity
The string is scanned from right to left, and each character is processed at most a constant number of times. Therefore, the time complexity isO(n)n is the length of the string. The
StringBuilder stores the resulting string, requiring O(n) space. Apart from the output, the algorithm uses O(1) extra space.
