【LeetCode】151. 翻转字符串里的单词

Dear 丶 2022-04-21 23:22 163阅读 0赞

**题目链接**：[https://leetcode-cn.com/problems/reverse-words-in-a-string/description/][https_leetcode-cn.com_problems_reverse-words-in-a-string_description]

#### 题目描述 ####

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

#### 示例 ####

输入: “the sky is blue”,  
输出: “blue is sky the”.

**说明**:

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

#### 解决方法 ####

**解题思路**：字符串

class Solution { 
    public:
        void reverseWords(string &s) { 
            //去掉首尾空格
            int k=-1;
            for (int i=0;i<s.size();i++)
                if (s[i]!=' '){ k=i;break;}
            if (k==-1) { s="";return;}  //特殊情况：全都是空格
            s.erase(0,k);
            for (int i=s.size()-1;i>=0;i--)
                if (s[i]!=' '){ k=i;break;}
            s.erase(k+1,s.size()-1-k);
            //开始翻转
            reverse(s.begin(),s.end());
            int begin=0;
            while(begin<s.size()){ 
                int end; //end指向单词后的第一个空格
                if (s.find(" ",begin)==string::npos) end=s.size();
                else end=s.find(" ",begin);
                reverse(s.begin()+begin,s.begin()+end); //翻转单词
                if (end==s.size()) break;
                for (int i=end;i<s.size();i++)  //begin指向下一个单词的第一个字母
                    if (s[i]!=' '){ begin=i;break;}
                s.erase(end,begin-end-1);//去除多余的空格
                begin-=(begin-end-1);
            }        
        }
    };

[https_leetcode-cn.com_problems_reverse-words-in-a-string_description]: https://leetcode-cn.com/problems/reverse-words-in-a-string/description/