Reverse Words in a String leetcode

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 - );

}

巴特西

Reverse Words in a String leetcode

最新文章

热门文章