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?
C Solution:
void reverse(char *s, char *e) {
while (s < e) {
*s ^= *e;
*e ^= *s;
*s++ ^= *e--;
}
}
void reverseWords(char *s) {
char *_s = s;
while (*s) {
char *t = s;
while (*(++t) && *t != ' ');
if (!*t) {
reverse(s, t - 1);
s = t;
break;
}
*t = 0;
reverse(s, t - 1);
*t = ' ';
s = t + 1;
}
reverse(_s, s - 1);
}
Python Solution:
class Solution:
# @param s, a list of 1 length strings, e.g., s = ['h','e','l','l','o']
# @return nothing
def reverseWords(self, s):
def rvs(s, l, r):
while l < r:
s[l], s[r] = s[r], s[l]
l += 1
r -= 1
rvs(s, 0, len(s) - 1)
i = 0
for j in range(1, len(s)):
if s[j] != ' ': continue
rvs(s, i, j - 1)
i = j + 1
rvs(s, i, len(s) - 1)
Summary:
- nothing to say.
LeetCode: 186. Reverse Words in a String II
近期评论