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--;
 }
 }
}

• Elegie: 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!
• IEatBagels: @Elegie if Leetcode accepted the results I guess we can consider it as working as intended?
• Sᴀᴍ Onᴇᴌᴀ: Please see What to do when someone answers. I have rolled back Rev 6 → 5

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