151. Reverse Words in a String - jiejackyzhang/leetcode-note GitHub Wiki

Given an input string, reverse the string word by word.

For example,

Given s = "the sky is blue",

return "blue is sky the".

Clarification:

• What constitutes a word? A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words? Reduce them to a single space in the reversed string.

解题思路为：

1. 先将前后空格删除，使用string的trim()方法；
2. 将整个string翻转；
3. 再将每个word翻转；
4. 最后将多余的空格删除；

public class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        s = s.trim();
        char[] array = s.toCharArray();
        reverse(array, 0, array.length-1);
        int start = 0, end = 0;
        while(end < array.length) {
            if(array[end] != ' ') {
                start = end;
                while(end < array.length && array[end] != ' ') end++;
                end--;
                reverse(array, start, end);
            }
            end++;
        }
        int i = 0;
        while(i < array.length) {
            if(array[i] == ' ') {
                sb.append(" ");
                while(i < array.length && array[i] == ' ') i++;
            } else {
                sb.append(array[i++]);
            }
        }
        return sb.toString();
    }
    
    public void reverse(char[] array, int start, int end) {
        while(start < end) {
            char c = array[start];
            array[start] = array[end];
            array[end] = c;
            start++;
            end--;
        }
    }
}