LeetCode Reverse Words in a String without using any java library 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 &lt; length){
            while( (end &lt; length) &amp;&amp; (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 &gt;0)
            sb.append(" ");
        while(end &gt;= start){
            sb.append(s.charAt(end));
            end--;
        }
    }
}
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 &lt;= 1) {
        return s;
    }
    StringBuilder sb = new StringBuilder(length);
    int start = 0;
    int end = 0;
    while (start &lt; length) {
        while (end &lt; length &amp;&amp; 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 &gt; 0)
        sb.append(' ');
    while (end &gt; 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 &lt;= 1) {
        return s;
    }
    int start = 0;
    int end = 0;
    while (start &lt; length) {
        while (end &lt; length &amp;&amp; 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 &gt; 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 &gt; start){
        char ch = s[start];
        s[start] = s[end2];
        s[end2] = ch;
        ++start;
    }


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