题干背景

力扣入口 - 151.翻转字符串里的单词

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

示例 1：
输入: “the sky is blue”
输出: “blue is sky the”

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

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

重要思路

答案解析是希望不使用辅助空间，空间复杂度要求为O(1)。
解题思路：移除多余空格 -》将整个字符串反转 -》将每个单词反转。
移除多余空格，可以适用erase，但是时间复杂度是O(n)，所以考虑使用双指针法，最后resize（重新设置）一下字符串的大小。

具体代码

/**
  * 不适用Java内置方法实现
  * <p>
  * 1.去除首尾以及中间多余空格
  * 2.反转整个字符串
  * 3.反转各个单词
  * @param s
  * @return
  */
 // 151. 翻转字符串里的单词
 public String reverseWords(String s){
     // 1. 去除首尾以及中间多余空格
     StringBuilder builder = removeSpace(s);
     // 2. 反转整个字符串
     reverseString(builder, 0, builder.length() - 1);
     // 3. 反转各个单词
     reverseEachWords(builder);
     return builder.toString();
 }
 private StringBuilder removeSpace(String s){
     int start = 0;
     int end = s.length() - 1;
     while(s.charAt(start) == ' ') start++;
     while(s.charAt(end) == ' ') end--;
     StringBuilder builder =  new StringBuilder();
     while(start <= end){
         char c = s.charAt(start);
         if(c != ' ' || builder.charAt(builder.length() - 1) != ' '){
             builder.append(c);
         }
         start++;
     }
     return builder;
 }
 /**
  * 反转字符串指定区间[start, end]的字符
  * @return
  */
 public void reverseString(StringBuilder sb, int start, int end){
     while(start < end){
         char temp = sb.charAt(start);
         sb.setCharAt(start, sb.charAt(end));
         sb.setCharAt(end, temp);
         start++;
         end--;
     }
 }
 private void reverseEachWords(StringBuilder sb){
     int start = 0;
     int end = 1;
     int n = sb.length();
     while(start < n){
         while(end < n && sb.charAt(end) != ' '){
             end++;
         }
         reverseString(sb, start, end - 1);
         start = end + 1;
         end = start + 1;
     }
 }