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
  • \$\begingroup\$ Hello. Unfortunately, I don't think the code is entirely correct, because some characters may be expressed with two code units, and those must not be reversed. See dzone.com/articles/the-right-way-to-reverse-a-string-in-java for more info. Good luck! \$\endgroup\$
    – Elegie
    Sep 20, 2019 at 14:20
  • \$\begingroup\$ @Elegie if Leetcode accepted the results I guess we can consider it as working as intended? \$\endgroup\$
    – IEatBagels
    Sep 20, 2019 at 14:36
  • \$\begingroup\$ Please see What to do when someone answers. I have rolled back Rev 6 → 5 \$\endgroup\$ Sep 20, 2019 at 15:56

1 Answer 1

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\$ Sep 20, 2019 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.