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


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

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