算法刷题-字符串-151.反转单词

题目

给一串字符串，里面有若干单词，以空格界定单词的结束，翻转其中的单词

输入：s = " hello world "
输出：“world hello”

需要注意的是，给定的字符串可能存在头空格、尾空格以及中间的空格数量不唯一的情况。

要点

因为有多余空格的存在，所以如果普通的处理遍历，需要创建一个新的string存放，并需要考虑去掉开头结尾以及中间重复空格的情况，需要注意多个条件
那么如果就在原始字符串上面修改的话，也还是要注意条件，这会就可以先去除多余空格，再翻转整个字符，再逐个翻转单词。

代码（O(1)版，在原始字符串上处理）

步骤就是先去掉所有多余空格，再反转整个字符串，再逐个单词内部进行反转到正确顺序

class Solution {
public:
    void removeEmpty(string &s) {
        int slow = 0, fast = 0;
        for (;fast < s.size(); fast++) {
            if (s[fast] != ' ') { //当fast遍历到字母开始操作
                if (slow > 0) s[slow++] = ' '; //当不是第一个单词的时候，手动添加一个空格
                while(s[fast] != ' ' && fast < s.size()) { //这里就是当fast遇到单词的时候，赋值给slow，直到这个单词结束
                    s[slow++] = s[fast++];
                }
            }
        }
        s.resize(slow); //这里直接slow而不是slow+1是因为最后while还给slow++了
    }

    void reverseString(string &s, int head, int end) {
        while (head < end) {
            swap (s[head], s[end]);
            head++;
            end--;
        }
    }
//这个是实际运行的成员函数
    string reverseWords(string s) {
        removeEmpty(s); //去重空格，定义在上面 
        reverseString(s, 0, s.size()-1); //反转字符串，定义在上面

        //对逐个单词内部逐个反转
        for (int start = 0, end = 0; end <= s.size(); end++) { 
        //注意这里end终止的条件为什么是<=size()
        //是因为需要有一个判断最后一个单词结束的标志，相当于一个空格一样，而这个s.size()就是这个标志
            if (s[end] == ' ' || end == s.size()) {
                reverseString(s, start, end-1);
                start = end + 1;
            }
        }
        return s;
    }
};

代码（O(N)版，需要注意的是判断条件

class Solution {
public:
    string reverseWords(string s) {
        string result = "";
        // auto it = s.end()-1;
        // string::iterator start1;
        // string::iterator end = s.end()-1;
        int count = 0;
        int pos = s.size()-1;
        int start = 0;
        while (pos >= 0) {
            if(s[pos] == ' ') { //当遇到' '开始处理，
                if(count != 0) { //如果count！=0,证明遇到的' '是一个单词的结尾标志，就进行如下处理
                    start = pos + 1;
                    result.append(s, start, count);
                    result += " ";
                }
                count = 0; //反正遇到了' '就让count=0
            }else { //如果没遇到' '，就让count++
                count++;
            }
            pos--;
        }
        if (count > 0) { //这里当遍历完之后，因为开头可能没有' '用来标志第一个单词的结束，这里手动添加
            result.append(s, pos+1, count);
        } else { //要么就是开头有多余空格，上面的while循环里会多给它加个''就删除
            result.erase(result.size()-1,1); //删除空格
        }
        return result;
    }
};