LeetCode Reverse Words in a String without using any java library

Question

The following problem is from LeetCode:

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"

The following code is working correctly, but its runtime is 8 ms, which is only faster than 42.44% of Java online submissions. How to make the following code faster?

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        int length = s.length();
        int start = 0;
        int end = 0;
        while(start < length){
            while( (end < length) && (s.charAt(end) != ' ')){
                end++;
            }
            doReverse(s, start, end -1, sb);
            start = ++end;
        }
        return sb.toString();
    }

    private void doReverse(String s, int start, int end, StringBuilder sb){
        if(start >0)
            sb.append(" ");
        while(end >= start){
            sb.append(s.charAt(end));
            end--;
        }
    }
}

Answer 1

First: if you look into StringBuilder.reverse() you'll encounter some extra work for some Unicode symbols needing two chars for a symbol (called a surrogate pair), which should not be reversed.

But let's not consider that.

• Provide exactly the needed capacity for StringBuilder.
• sb.append(' ') is faster than for " ".
• end - 1 not needed.

So:

public String reverseWords(String s) {
    int length = s.length();
    if (length <= 1) {
        return s;
    }
    StringBuilder sb = new StringBuilder(length);
    int start = 0;
    int end = 0;
    while (start < length) {
        while (end < length && s.charAt(end) != ' ') {
            ++end;
        }
        doReverse(s, start, end, sb);
        start = ++end;
    }
    return sb.toString();
}

private void doReverse(String s, int start, int end, StringBuilder sb) {
    if (start > 0)
        sb.append(' ');
    while (end > start){
        --end;
        sb.append(s.charAt(end));
    }
}

In general using toCharArray could be faster:

public String reverseWords(String str) {
    char[] s = s.toCharArray();
    int length = s.length;
    if (length <= 1) {
        return s;
    }
    int start = 0;
    int end = 0;
    while (start < length) {
        while (end < length && s.charAt(end) != ' ') {
            ++end;
        }
        doReverse(s, start, end);
        start = ++end;
    }
    return new String(s);
}

private void doReverse(char[] s, int start, int end) {
    while (--end > start){
        char ch = s[start];
        s[start] = s[end];
        s[end] = ch;
        ++start;
    }
}

If you would inline doReverse for extra speed, you would need a copy of the changing parameters.

    // doReverse(char[] s, int start, int end)
    int end2 = end;
    while (--end2 > start){
        char ch = s[start];
        s[start] = s[end2];
        s[end2] = ch;
        ++start;
    }

Now we should be twice as fast (wild guess).