3
\$\begingroup\$

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--;
        }
    }
}
\$\endgroup\$
3
2
\$\begingroup\$

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).

\$\endgroup\$
1
  • \$\begingroup\$ thank your for your answer, lot of learning. \$\endgroup\$ – Neelabh Singh Sep 20 '19 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.