151-颠倒字符串中的单词

LeetCode 151. 颠倒字符串中的单词

给你一个字符串 s ，颠倒字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：颠倒后的字符串中不能存在前导空格和尾随空格。

method

• 先去掉多余的空格
• 整体反转
• 反转每个单词

void reverse(string& s, int i, int j) {
    while (i < j) {
        swap(s[i], s[j]);
        i++;
        j--;
    }
}
void removeSpace(string& s) {
    int i = 0, j = 0;
    int n = s.size();
    while (i < s.size() && s[i] == ' ') i++;
    for (; i < n; i++) {
        if (i > 0 && s[i] == ' ' && s[i] == s[i - 1]) continue;
        s[j++] = s[i];
    }
    if (j - 1 >= 0 && s[j - 1] == ' ') s.resize(j - 1);
    else s.resize(j);   // 如果后面有多余的空格，会留下一个，也要去掉
}
string reverseWords(string s) {
    removeSpace(s);	// 去掉前后以及中间的多余空格
    int n = s.size();
    reverse(s, 0, n - 1);
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && s[j] != ' ') j++;
        reverse(s, i, j - 1);
        i = j;
    }
    return s;
}

时间复杂度：$\mathcal{O}(n)$
空间复杂度：$\mathcal{O}(1)$

---

LeetCode 186. 翻转字符串里的单词 II

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

示例：

输入: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
输出: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

method

void func(vector<char>& s, int i, int j) {
    while (i < j) {
        swap(s[i], s[j]);
        i++, j--;
    }
}
void reverseWords(vector<char>& s) {
    reverse(s.begin(), s.end());
    int i = 0;
    int n = s.size();
    while (i < n) {
        int start = i;
        while (i < n && s[i] != ' ') i++;
        func(s, start, i - 1);	// 如果i==n，后面[start, i-1]的反转还是正确的，然后就退出了
        i++;
    }
}