Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input:
 "Let's take LeetCode contest"

Output:
 "s'teL ekat edoCteeL tsetnoc"

Note:In the string, each word is separated by single space and there will not be any extra space in the string.

Analysis

也不知为什么Reverse Words in a String I， II，III系列一道比一道简单...用I，II中的Two Pointers方法瞬间就可以解出来。

O(n) time - 嵌套循环时每个元素最多遍历三次（一次右指针，一次左指针，还有一次是swap/reverse时）

O(n) space - 用了辅助以及存结果用的char array

Solution

Two Pointers - Reverse - O(n) time, O(n) space - (8ms)

class Solution {
    public String reverseWords(String s) {
        int i = 0, j = 0;
        int n = s.length();
        char[] chs = s.toCharArray();
        while (i < n && j < n) {
            while (i < n && chs[i] == ' ') {
                i++;
            }
            j = i;
            while (j < n && chs[j] != ' ') {
                j++;
            }
            reverse(chs, i, j - 1);
            i = j;
        }
        return new String(chs);
    }

    private void reverse(char[] chs, int s, int t) {
        while (s < t) {
            char tmp = chs[s];
            chs[s] = chs[t];
            chs[t] = tmp;
            s++;
            t--;
        }
    }
}

当然还有用原生的函数法 (13ms)

    public String reverseWords(String s) {
        String[] str = s.split(" ");
        for (int i = 0; i < str.length; i++) str[i] = new StringBuilder(str[i]).reverse().toString();
        StringBuilder result = new StringBuilder();
        for (String st : str) result.append(st + " ");
        return result.toString().trim();
    }