0151-翻转字符串里的单词

题目链接

题目描述

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
说明：

• 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
• 翻转后单词间应当仅用一个空格分隔。
• 翻转后的字符串中不应包含额外的空格。

  示例

  示例1：

  输入：s = “the sky is blue” 输出：“blue is sky the”

提示

• 1 <= s.length <= 10
• s 包含英文大小写字母、数字和空格 ' '

• s 中 至少存在一个 单词

  思路

  本题调用几个api就能完成，但本题就失去的意义，因此，我们最好还是实现一些方法。

  思路1：双指针

  首先，我们要移除多余的空格，可以选用快慢指针来实现，如0027-移除元素一题。
  然后，我们需要将字符串反转，可以选用双指针实现，如0344-反转字符串一题。
  最后，我们要将每个单词反转回来。

  思路2：正则表达式

  匹配非空格的字符，然后逆序输出，此方法复杂度较高，不建议使用。

  题解

  思路1：双指针

  class Solution {
   private:
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; ++i, --j) {
            swap(s[i], s[j]);
        }
    }
    void removeBlank(string& s) {
        int slow = 0, fast = 0;
        while (s.size() > 0 && fast < s.size() && s[fast] == ' ') {
            ++fast;
        }
        while (fast < s.size()) {
            if (fast - 1 > 0 && s[fast - 1] == ' ' && s[fast] == ' ') {
            } else {
                s[slow++] = s[fast];
            }
            ++fast;
        }
        if (slow - 1 > 0 && s[slow - 1] == ' ') {
            s.resize(slow - 1);
        } else {
            s.resize(slow);
        }
    }
   public:
    string reverseWords(string s) {
        removeBlank(s);
        reverse(s, 0, s.size() - 1);
        for (int i = 0; i < s.size(); ++i) {
            int j = i;
            while (j < s.size() && s[j] != ' ') {
                ++j;
            }
            reverse(s, i, j - 1);
            i = j;
        }
        return s;
    }
  };

  思路2：正则表达式

  class Solution {
   public:
    string reverseWords(string s) {
        vector<string> v;
        regex r("[^\\s]+");
        sregex_iterator it(s.begin(), s.end(), r);
        sregex_iterator end;
  
        while (it != end) {
            v.emplace_back(it->str(0));
            ++it;
        }
        string ans;
        for (int i = v.size() - 1; i >= 0; --i) {
            ans.append(v[i] + " ");
        }
        ans.pop_back();
  
        return ans;
    }
  };
  

  复杂度分析

  思路1：双指针

• 时间复杂度：

• 空间复杂度：