LeetCode 151.Reverse Words in a String (翻转字符串里的单词)-蒲公英云

LeetCode 151.Reverse Words in a String (翻转字符串里的单词)

小鱼儿 2022-05-08 19:44 315阅读 0赞

题目描述：

给定一个字符串，逐个翻转字符串中的每个单词。

示例:

输入: "the sky is blue",
输出: "blue is sky the".

说明:

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。

AC C++ Solution:

思路：
先反转整个字符串，再反转每个单词

Code:

class Solution {
public:
    void reverseWords(string &s) {
        reverse(s.begin(),s.end());
        int storeIndex = 0;                     //storeIndex: 重新反转存储的下标
        for (int i = 0; i < s.size(); i++) {    
            if (s[i] != ' ') {
                if(storeIndex != 0)
                    s[storeIndex++] = ' ';      //如果这个单词不是第一个单词，则在单词前面放一个空格。
                int j = i;                      //j:一个单词的结尾; i:一个单词的开头
                while(j < s.size() && s[j]  != ' '){
                    s[storeIndex++] = s[j++];
                }
                reverse(s.begin() + storeIndex - (j-i), s.begin() + storeIndex);        //反转一个单词
                i = j;                          
            }
        }
        s.erase(s.begin() + storeIndex, s.end());           //删除重新排序后的后缀多余部分
    }
};