https://leetcode.cn/problems/reverse-words-in-a-string/description/

<aside> 💡

这题难点有两个：

1. 如何去除多余空格？
   • 前置空格
   • 尾置空格
   • 单词间的多余空格
2. 如何反转单词 </aside>

非原地修改思路：创建一个空字符串，将原字符串的单词逐个拼接到新字符串的头部

string reverseWords(string s) {
	string ans = "";
	string temp;

	for (int i = 0; i < s.size(); ++i) {
    // 忽略所有空格，单词间的空格后面手动加
		if (s[i] == ' ')
			continue;
		else {
      // 记录单词
			temp = "";
			while (i < s.size() && s[i] != ' ') {
				temp = temp + s[i];
				++i;
			}
      // 非首个单词就在前面加上空格
			if (!ans.empty())
				ans = " " + ans;
      // 将记录下来的单词拼接到新字符串的头部
			ans = temp + ans;
		}
	}
	return ans;
}

<aside> 💡

原地修改思路：

1. 如何去除空格——快慢指针
2. 如何反转单词——先字符串整体反转，再每个单词逐个反转 </aside>

string reverseWords(string s) {
    int slow = 0;
    // 去除多余空格——快慢指针
    for (int fast = 0; fast < s.size(); ++fast) {
        // 快指针跳过所有空格
        if (s[fast] == ' ') {
            continue;
        }

        // 如果不是第一个单词，则在前面补一个空格
        if (slow != 0) {
            s[slow++] = ' ';
        }

        // 将当前单词前移到慢指针处
        while (fast < s.size() && s[fast] != ' ') {
            s[slow++] = s[fast++];
        }
    }
    s = s.substr(0, slow);

    // 反转单词——先字符串整体反转，再每个单词逐个反转
    std::reverse(s.begin(), s.end());
    slow = 0;
    for (int fast = 0; fast < s.size(); ++fast) {
        while (fast < s.size() && s[fast] != ' ') {
            ++fast;
        }
        std::reverse(s.begin() + slow, s.begin() + fast);
        slow = fast + 1;
    }
    return s;
}