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 = "
return "
Given s = "
the sky is blue",return "
blue is sky the".
Could you do it in-place without allocating extra space?
Code (Java):
public class Solution {
public void reverseWords(char[] s) {
if (s == null || s.length <= 1) {
return;
}
int i = 0;
int j = s.length - 1;
while (i < j) {
swap(s, i, j);
i++;
j--;
}
// Step 2: swap again within a token
i = 0;
j = 0;
while (j < s.length) {
while (j < s.length && s[j] != ' ') {
j++;
}
int m = i;
int n = j - 1;
while (m < n) {
swap(s, m, n);
m++;
n--;
}
i = j + 1;
j = i;
}
}
private void swap(char[] s, int i, int j) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
}
No comments:
Post a Comment