Reverse Words in a String leetcode

时间:2023-11-10 23:21:20

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.
这个题如果用C++的stringstream字符串流来实现的话,会非常简单
void reverseWords(string &s) {
istringstream is(s);
string tmp;
is >> s;
while(is >> tmp) s = tmp + " " + s;
if(s[] == ' ') s = "";
}

但是,题目中对于C语言实现有更严格的要求,需要就地操作

联想到之前碰到的题目,数组旋转问题,我们是否可以用类似的思路来解决呢

对于每一个单词,都将其字母前后逆置,然后再将整个字符串逆置,这样就可以得到正确反转结果了。

但是如何处理多余的空格呢?我们可以在遍历的同时,利用快慢双指针来将空格省略掉。然后再执行逆置操作。

代码如下:

void reverseWords(string &s) {

    int i = , j = ;
int l = ;
int len = s.length();
int wordcount = ; while (true) {
while (i<len && s[i] == ' ') i++;
if (i == len) break;
if (wordcount) s[j++] = ' ';
l = j;
while (i<len && s[i] != ' ') { s[j] = s[i]; j++; i++; }
reverseword(s, l, j - );
wordcount++;
}
s.resize(j);
reverseword(s, , j - );
}