151. 颠倒字符串中的单词

151. 颠倒字符串中的单词

题目：给你一个字符串 s ，颠倒字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格

题解： 给一个由单词组成的字符串，每两个单词中间至少有一个空格；字符串收尾也可能有空格；要求把字符串反转，反转后每两个单词中间只能有一个空格，字符串首尾不能有空格

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

解题思路：
示例 ：" the sky is blue"

1. 先检查字符串是否为空，空字符串就直接 return 空串
2. 先检查首尾是否用空格，有就去掉 "the sky is blue"
3. 反转整个字符串 "eulb si yks eht"
4. 逐个反转单词 "blue is sky the"
5. 如此看来需要写一个通用的反转字符串函数，然后按照以上逻辑执行就可解决问题

class Solution {
   /**
    思路：
    1.先检查字符串是否为空
    2.检查首尾是否有空格，有就去掉 因为反转后首尾不能有空格题目要求
    3.反转整个字符串
    4.逐个单词反转
    如此看来需要写一个通用的反转字符串函数，然后按照以上逻辑执行就可以解决问题
    */
   public String reverseWords(String s) {

       //0.处理边界问题
       if(s==null) return null;
       //1.定义需要的数据结构
       char[] list = s.toCharArray();
       //2.检查首尾是否有空格，有就去掉 因为反转后首尾不能有空格题目要求
       int length = 0;//字符串最终的有效长度
       int curr = 0;//当前可以用来存放字符的位置
       boolean space = true;//前一个是否是空格字符，直接给true是为了避免第一个字符是空格的情况
       for(int i = 0;i < list.length;i++) {
          if(list[i] != ' ') {//非空格
            list[curr] = list[i];
            curr++;
            space = false;
          }else if(space == false) {//当前i是空格字符，i-1是非空格字符
            list[curr] = ' ';
            curr++;
            space = true;
          }
       }

       //最后一位是空格，字符串的真实长度是curr-1
       length = space ? (curr-1):curr;
       //没有有效长度直接返回空串
       if(length <= 0) return "";

       //3.反转整个字符串
       reverse(list,0,length);

       //4.逐个单词反转
       int prevSapceIdx = -1;//定义哨兵，即前一个空格字符的位置
       for(int i = 0; i < length; i++){
           if(list[i] != ' ') continue;
           //i 来到这里就说明是空格 这时就拿到了一个单词的位置 [prevSapceIdx,i)
           reverse(list,prevSapceIdx,i);
           //记录空格的位置
           prevSapceIdx = i;
       }

       //至此 除了最后一个单词其他都逆序好了，所以需要再走一次reverse
       reverse(list,prevSapceIdx+1,length);

       //5.返回结果
       return new String(list,0,length);

   }
   
   //逆序[li,ri)范围内的字符 左闭右开
   private void reverse(char[] chars,int li, int ri) {
      ri--;//由于是左闭右开区间，进来先移动ri向左一步
      while(li < ri) {
          char tmp = chars[li];
          chars[li] = chars[ri];
          chars[ri] = tmp;
          li++;
          ri--;
      }

   }

}