leetcode 151. 翻转字符串里的单词

[xxleyi]

题：

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

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"
示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 

说明：

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

进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-words-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解：

如果不考虑特别高效的实现，此题不难。但恰好是一个训练「循环不变式」的好例子：循环不变式与题目答案有一定差距。

具体可以看代码：

• 循环前的初始化比较简单
• 循环中的正确更新也不算复杂
• 循环结束之后，循环不变式也依旧成立，但 termination + loop invariant => goal 在这里明确的体现出来：想得到最终正确的答案，仍然需要妥善处理一下

// 循环不变式保证正确得到答案
var reverseWords = function(s) {
  // 存储所有单词
  let words = []
  // 用于缓存单个单词
  let word = []
  // 循环不变式：上一个空格之后，未遇到空格之前，所有字母都存储在 word 中
  // 遇到空格，且 word 非空时，words 中将新增一个单词
  for (let e of s) {
    // 每一次循环均正确更新 wrod 以确保循环不变式成立
    if (e === ' ' && word.length !== 0) {
      words.push(word.join(''))
      word = []
    } else if (e !== ' ') {
      word.push(e)
    }
  }
  // 循环终止：若最后一个 word 非空，words 中需新增一个单词
  if (word.length) words.push(word.join(''))

  // 得到正确答案：reverse 单词数组，并拼接成字符串
  words = words.reverse().join(' ')
  return words
};

// 内置字符串处理方法
var reverseWords = function(s) {
  return s.trim(' ').split(/\s+/).reverse().join(' ')
}