LeetCode Reverse Words in a String III

本篇為LeetCode上演算法的簡單問題，Reverse Words in a String III，字串反轉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.

這題字串反轉是要將一段句子中的每個單字前後反轉就好，而不是將整段句子反轉。例如輸入"Let's take LeetCode contest"，則輸出應為"s'teL ekat edoCteeL tsetnoc"。

此題一開始想到的解法就是用String.split()去分割句子中的每個單字為字串陣列，再將字串陣列中的每個單字反轉後重組。

public static String reverseWords(String s) {
    String[] ss = s.split("\\s");
    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < ss.length; i++) {
        char[] cc =  ss[i].toCharArray();
        int lastIndex = cc.length - 1;
        for(int j = 0; j < cc.length/2; j++ ) {
            cc[j] ^= cc[lastIndex - j];
            cc[lastIndex - j] ^= cc[j];
            cc[j] ^= cc[lastIndex - j];
        }
        sb.append(" ").append(cc);
    }
    return sb.substring(1);
}

但這樣的解法效能不好，因為在String.split()中會跑迴圈，又加上外面用來返轉單字的迴圈，時間複雜度大於O(N)。

第二個解法是先用StringBuilder.reverse()先將整段句子反轉後再以String.split()進行分割並以對的順序重組。

public static String reverseWords(String s) {
    StringBuilder sb = new StringBuilder();
    String[] ss = sb.append(s).reverse().toString().split("\\s");
    int lastIndex = ss.length - 1;
    sb = new StringBuilder();
    for(int i = lastIndex; i >= 0; i--) {
        sb.append(" ").append(ss[i]);
    }
    return sb.substring(1);
}

雖然比第一次的解法快了一些，但仍只有36%的勝率。

第三個解法是參考多數人的寫法，從句子頭開始每個字元判斷，若該字元為空白，則將空白前的單字進行反轉，例用兩個變數來暫存每個單字的開頭和結束的索引位置，而句字的最後一個字要做額外的判斷。

public static String reverseWords(String s) {
        
    char[] cc = s.toCharArray();
    for(int end = 0, start = 0; end < cc.length; end++ ) {
        if(cc[end] == ' ') {
            reverseWord(start, end - 1, cc);
            start = end + 1;
        }
        if(end == cc.length - 1) {
           reverseWord(start, end, cc);
        }
    }
    return String.valueOf(cc);
}

public static void reverseWord(int start, int end, char[] cc) {
    while(start < end) {
        char temp = cc[start];
        cc[start] = cc[end];
        cc[end] = temp;
        start++;
        end--;
    }
}

此方法的beats率為65%。

下面的解法是例用StringBuilder.insert(int offset, char c)將每個字元插最前頭直到碰到空白，但效果也是不好。

public static String reverseWords(String s) {

    char[] cc = s.toCharArray();
    StringBuilder msb = new StringBuilder();
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < cc.length; i++) {
        if (cc[i] == ' ') {
            msb.append(sb).append(" ");
            sb = new StringBuilder();
            i++;
        }
        sb.insert(0, cc[i]);
        if (i == cc.length - 1) {
            msb.append(sb.toString());
        }
    }
    return msb.toString();
}

參考：

• LeetCode Reverse String 字串反轉