翻转单词顺序

---

题目：

解题：

1、双指针

• 解题思路：

  • 倒序遍历字符串 s ，记录单词左右索引边界 i , j ；
  • 每确定一个单词的边界，则将其添加至单词列表 res ；
  • 最终，将单词列表拼接为字符串，并返回即可。

• 复杂度分析：

  • 时间复杂度 O(N) ： 其中 N 为字符串 s 的长度，线性遍历字符串。
  • 空间复杂度 O(N) ： 新建的 StringBuilder 中的字符串总长度 ≤N ，占用 O(N) 大小的额外空间。

• 代码：

  // 双指针
  class Solution {
      public String reverseWords(String s) {
          // 删除首尾空格
          s = s.trim();
          int j = s.length() - 1;
          int i = j;
          StringBuilder res = new StringBuilder();
          while(i >= 0) {
              // 让i走到首个空格
              while (i >= 0 && s.charAt(i) != ' ') i--;
              // 添加单词
              res.append(s.substring(i+1,j+1) + " ");
              // 跳过单词间的空格
              while (i >= 0 && s.charAt(i) == ' ') i--;
              // j 指向下个单词的尾字符
              j = i;
          }
          // 消除最后多余的一个的空格
          return res.toString().trim();
      }
  }

2、分割 + 倒序

• 解题思路：

  • 

• 复杂度分析：

  • 时间复杂度 O(N)

• 空间复杂度 O(N) ： 单词列表 strs 占用线性大小的额外空间。

• 代码：

  // 分割 + 倒序
  class Solution2 {
      public String reverseWords(String s) {
          // 删除首尾空格，分割字符串
          String[] strs = s.trim().split(" ");
          // 拼接时所需
          StringBuilder res = new StringBuilder();
          for (int i = strs.length - 1; i >= 0; i--) {
              if (strs[i].equals("")) continue;
              res.append(strs[i] + " ");
          }
          // 消除最后多余的一个的空格
          return res.toString().trim();
      }
  }