ReverseWordsInAStringIII [source code]

public class ReverseWordsInAStringIII {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        String res = "";
        for (int i = 0; i < words.length - 1; i++) res += (reverseWord(words[i]) + " ");
        return res + reverseWord(words[words.length-1]);
    }

    public String reverseWord(String word) {
        int i = 0, j = word.length() - 1;
        char[] characters = word.toCharArray();
        char tmp; 
        while (i < j) {
            tmp = characters[j];
            characters[j] = characters[i];
            characters[i] = tmp;
            i++;
            j--;
        }
        return new String(characters);
    }

    public static void main (String[] args) {
        ReverseWordsInAStringIII tester = new ReverseWordsInAStringIII();
        String input1 = "Let's take LeetCode contest";
        System.out.println(tester.reverseWords(input1));
    }
}

这个算法总体是比较简单的, 不过我这个写法最后的时间特别长, 接近300ms, 10%的速度;

下面这个是一个思路类似(依赖于 split 和 reverse, 只不过多利用了标准库函数):

public class Solution {  
    public String reverseWords(String s) {  
        String words[] = s.split(" ");  
        StringBuilder res=new StringBuilder();  
        for (String word: words)  
            res.append(new StringBuffer(word).reverse().toString() + " ");  
        return res.toString().trim();  
    }  
}

注意这里这个 trim 的应用: 避免了长期困扰我的结尾问题, 至少在这里是可以用的, 因为这里的 seperator 是空格;

public class Solution {  
    public String reverseWords(String s) {  
        char[] ca = s.toCharArray();  
        for (int i = 0; i < ca.length; i++) {  
            if (ca[i] != ' ') {   // when i is a non-space  
                int j = i;  
                while (j + 1 < ca.length && ca[j + 1] != ' ') { j++; } // move j to the end of the word  
                reverse(ca, i, j);  
                i = j;  
            }  
        }  
        return new String(ca);  
    }  

    private void reverse(char[] ca, int i, int j) {  
        for (; i < j; i++, j--) {  
            char tmp = ca[i];  
            ca[i] = ca[j];  
            ca[j] = tmp;  
        }  
    }  
}

这个是一个基于类似2pointers的算法, 有点类似425project 的时候 guoye 用来预处理文件的算法, 不过要简单一些.
这里要学习的是:

1. String 问题上来就直接转换成char array往往处理起来方便很多;
2. 注意他这里 reverse 这个函数的 API 的设计, 通过可以指定begin and end, 来让这个函数可以直接应用在整个大 string 上面;

但是这还没完, 这个问题其实很有启示意义: 仔细看看上面这个算法, 对比前面学 KMP 算法的时候的经验, 可以看到上面这个算法有一个很大的问题, 速度明显有改善的空间: 太多的 backup;

    public String reverseWords(String s) {  
        int n = s.length();  
        char[] c = s.toCharArray();  
        for (int i = 0, j = 1; j <= n; j++) {  
            if (j == n || c[j] == ' ') {  
                reverse(c, i, j-1);  
                i = j+1;  
            }  
        }  
        return new String(c);  
    }  

    private void reverse(char[] c, int i, int j) {  
        while (i < j) {  
            char temp = c[i];  
            c[i] = c[j];  
            c[j] = temp;  
            i++; j--;  
        }  
    }

这个算法就是改善了这个问题, 虽然没有 KMP 那么复杂, 但是在整个算法的复杂度理论上是从平方降到了linear;

Problem Description

Given a string, you need to reverse the order of characters in each word within a sentence while still reserving 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.

Subscribe to see which companies asked this question.

Hide Tags String
Hide Similar Problems (E) Reverse String II