151. Reverse Words in a String

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();

        for (int j = s.length() - 1; j >= 0; j--) {
            if (s.charAt(j) != ' ') {
                // 找到单词右边界
                if (sb.length() != 0) {
                    sb.append(" ");
                }

                int i = j; // word: [i, j]
                while (i >= 0 && s.charAt(i) != ' ') {
                    i--;
                }

                // now: i == -1 or s.charAt(i) == ' '
                sb.append(s, i + 1, j + 1);
                j = i;
            }
        }

        return sb.toString();
    }
}

class Solution {
    public String reverseWords(String s) {
        // 输入：s = " hello world " 输出："world hello"
        char[] chars = s.toCharArray();
        reverse(chars, 0, chars.length - 1); // " dlrow olleh "

        int writeIndex = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != ' ') {
                // 找到一个单词起始点
                if (writeIndex != 0) {
                    chars[writeIndex++] = ' ';
                }

                int j = i;
                while (j < chars.length && chars[j] != ' ') {
                    j++;
                }
                // now: j == chars.length || chars[j] == ' '

                reverse(chars, i, j - 1);
                for (int k = i; k < j; k++) {
                    chars[writeIndex++] = chars[k];
                }

                i = j; // 不要忘记重置 i 索引，因为读取了一个单词
            }
        }

        return new String(chars, 0, writeIndex);
    }

    private void reverse(char[] chars, int i, int j) {
        while (i < j) {
            swap(chars, i++, j--);
        }
    }

    private void swap(char[] chars, int i, int j) {
        char tmp = chars[i];
        chars[i] = chars[j];
        chars[j] = tmp;
    }
}

References

151. Reverse Words in a String
剑指 Offer 58 - I. 翻转单词顺序