剑指offer-44、翻转单词序列

题⽬描述

给定⼀个句⼦，将句⼦中的单词进⾏翻转，注意，单词内部的字符顺序不改变，改变的是单词与单词之间的顺序，⽐如“ I am a coder. ”,翻转之后变成“ coder. a am I ”。
示例
注意：引号内部才是输⼊的内容
输⼊："You are a cool boy."
输出："boy. cool a are You"
思路及解答

Java内置函数分割反转

Java ⾥⾯有切割字符串的⽅法，直接⽤空格进⾏分隔，分隔成为多个单词，然后从字符串数组的后⾯开始，每⼀个字符拼接上⼀个空格，但是，值得注意的⼀点是，当只剩下⼀个字符串的时候，也就是索引为 0 的时候，不需要再拼接空格。代码实现如下：

1. public class Solution {
2.     public String ReverseSentence(String str) {
3.         if (str == null || str.length() == 0 || str.equals(" ")) {
4.                 return "";
5.         }
6.         
7.         //去除首尾空格后，按照空格分隔
8.         String[] strs = str.trim().split(" ");
9.         StringBuilder stringBuilder = new StringBuilder();
10.         for (int i = strs.length - 1; i >= 0; i--) {
11.             stringBuilder.append(strs[i]);
12.             stringBuilder.append(i == 0 ? "" : " ");
13.         }
14.         return stringBuilder.toString();
15.     }
16. }

复制代码

• 时间复杂度：O(n)，分割和拼接各需线性时间
  
• 空间复杂度：O(n)，存储单词数组和结果字符串
  

借助栈

借助栈，栈是先进后出，也就是我们切割完字符串之后，全部放到栈中，再全部取出来拼接，就可以完成逆序的操作。有⼀个值得注意的点，就是空格的问题，我们压栈的时候，跟随着拼接上空格即可，最后⼀个字符不压⼊空格。

1. public String ReverseSentence(String str) {
2.     if (str == null || str.length() == 0)
3.         return str;
4.     StringBuilder stringBuilder = new StringBuilder();
5.     String[] strs = str.split(" ");
6.     if (strs.length == 0)
7.         return str;
8.     Stack < String > stack = new Stack < > ();
9.     for (int i = 0; i < strs.length - 1; i++) {
10.         stack.push(strs[i]);
11.         stack.push(" ");
12.     }
13.     stack.push(strs[strs.length - 1]);
14.     while (!stack.isEmpty()) {
15.         stringBuilder.append(stack.pop());
16.     }
17.     return stringBuilder.toString();
18. }

复制代码

双指针法(推荐)

⾸先判断字符串 str 是否为空或者为空字符，如果 str 不为空，则初始化 start ，和 end 指针指向字符串的尾部， start 从尾部向头部遍历
针对每⼀个字符，如果字符为空字符：

• 如果 start 和 end 不是出于同⼀个位置，说明已经遍历完⼀个单词，那么将 start+1 ~ end 之间的字符，拼接到结果后，并且添加上⼀个空格。将 start-1 ，并且 end 指向 start 的位置
  
• 否则，说明是多余的空格，直接跳过， start-1 ， end=start
  

如果字符不是空字符：可以把 start 索引前移，也就是 start--
最后，剩下最后⼀个单词的时候，需要特殊处理最后⼀个单词，拼接到字符串后⾯就可以了。
[code]public class Solution {    public static void main(String[] args) {        Solution solution = new Solution();        System.out.println(solution.ReverseSentence("nowcoder. a am I"));    }    public String ReverseSentence(String str) {        if (str != null && str.length() != 0 && !str.equals(" ")) {            int start = str.length() - 1, end = start;            StringBuffer stringBuffer = new StringBuffer();            for (; start > 0;) {                // 如果为空格                if (str.charAt(start) == ' ') {                    // 且开始索引和结束索引不⼀致的情况                    if (start != end) {                        // 遍历start+1~end的字符，加到                        for (int i = start + 1; i

这个好，看起来很实用