Problem151: Reverse Words in a String

https://leetcode.com/problems/reverse-words-in-a-string/

这道题非常disgusting，有无数的corner cases要去考虑。但这种题目是准备的关键。

思路

这道题的思路有很多，第一种是考虑各种的corner cases，比如首尾有没有space啦，中间隔着很多space啦等等。但是实际上正面做的时候，还是感觉到很难把所有的情况都考虑到，容易出错。

第二种思路，类似于快慢指针的办法。先设置一个start指针，从末尾往前走，因为有可能有trailing spaces，所以真正当他遇到第一个不为空的character的时候，这时候，我们设置另一个指针end。接下来，让start指针继续向前走，直到start遇到下一个空格，这时，start和end之间的词就被定位了，它将是answer的第一个词。以此类推。

public class Solution {
    public String reverseWords(String s) {
        if (s.length() == 0 || s == null) {
            return s;
        }

        StringBuilder sb = new StringBuilder();
        for (int start = s.length() - 1; start >= 0; start--) {
            if (s.charAt(start) == ' ') {
                continue;
            }
            int end = start;
            while (start >= 0 && s.charAt(start) != ' ') {
                start--;
            }
            sb.append(s.substring(start + 1, end + 1) + " ");
        }

        return sb.toString().trim();
    }
}

易错点

1. 空指针查看是非常必要的

   if (s.length() == 0 || s == null) {
       return s;
   }

2. substring 的index问题 substring(beginIndex, endIndex); beginIndex-包含；endIndex-不包含 [a, b)

   String s = "Hello World";
   
   System.out.println(s.substring(0));  // Hello World
   System.out.println(s.substring(1));  // ello World
   System.out.println(s.substring(0, 2)); // He
   System.out.println(s.substring(0, 4)); // Hell

   这道题里，

   sb.append(s.substring(start + 1, end + 1) + " ");

   start + 1 是因为start已经挪到了空白处; end + 1是因为右边是开区间

3. 去除空白的函数 trim()

4. StringBuider的用处

   StringBuilder sb = new StringBuilder();

   创建一个StringBuilder

   sb.append(s.substring(start + 1, end + 1) + " ");

   不断地append这个builder

   sb.toString();

   再把StringBuilder变成字符串

5. char 和 String 的区别 如果用' '表示的是char，相反用" "表示的是String

6. 要把 StringBuilder 放在外面，这样才不会因为每次新建一个StringBuilder 而丢失结果