Questions¶
Difficulty: Medium
Given an input string, reverse the string word by word.
For example,
Given s
= "the sky is blue"
,
return "blue is sky the"
.
For C programmers: Try to solve it in-place in O(1) space.
Clarification:
- What constitutes a word? A sequence of non-space characters constitutes a word.
- Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces.
- How about multiple spaces between two words? Reduce them to a single space in the reversed string.
Coding¶
C¶
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
* 反转字符串的指定长度
*/
void reverse(char* s, int start, int end){
char t;
for(;start<end;start++,end--){
t = s[start];
s[start] = s[end];
s[end] = t;
}
}
void reverseWords(char *s) {
if(s == NULL){
return;
}
int n = strlen(s);
int i = 0, j = strlen(s) - 1, t = 0, r = 0;
/* 消除字符串末尾的空格 */
while(s[j] == ' '){
s[j] = '\0';
j -= 1;
}
/* 消除字符串开始的空格 */
while(s[i] == ' '){
i++;
}
n = strlen(s);
r = t + i;
while(n > 0){
/* 消除字符串中间的多个空格 */
while(s[r] == ' ' && s[r+1] == ' '){
r++;
}
s[t] = s[r];
t++;
r++;
n--;
}
s[t] = '\0';
i = 0;
n = strlen(s);
while(i < n){
j = i;
while(j < n){
if(s[j] == ' '){ /* 使用单引号表示空格字符 */
break;
}else{
j++;
}
}
reverse(s, i, j-1);
while(j < n && s[j] == ' '){
j++;
}
i = j;
}
reverse(s, 0, n - 1);
}
int main(){
char* s = (char *)malloc(100 * sizeof(char));
gets(s);
printf("s [%s]\n", s);
reverseWords(s);
printf("s [%s]\n", s);
return 0;
}
python¶
# -*- coding: utf-8 -*-
# for one line
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
return ' '.join(i for i in s.split(' ')[::-1] if i != '')