# Reverse words in a string

• For approach 2, I feel the complexity would be O(n^2) - Since, you are looping over each character of the word in 'reverse()' for every word in the string.

• @ravit.thapar-gmail.com Looping over each character of the word in reverse() for every word will take O(n) where n is total number of characters.

• @vinod23 Could you explain a little more? I was under the impression that since reverse() is nested in the for loop of reverseWords() it would be O(n^2)

• public static String reverseWords(String s){
String[] strs = s.split(" ");//按空格进行分割
StringBuilder sb = new StringBuilder();
for(String str:strs){
sb.append(new StringBuilder(str).reverse()).append(" ");
}
return sb.toString().substring(0,sb.toString().length()-1);

``}``

• Split string at space, then use stack to reverse single word.

• This solution creates n amount of String Objects. One solution is to use StringBuilder with method append or even use an array of chars

• @vinod23 Yes, that's correct. And since it is doing that operation for every word (say for 'm' words), hence the overall complexity of the algorithm becomes O(n*m).

• One-line solution in python: `return " ".join([i[::-1] for i in s.split()])`

• The second solution seems overly complicated. Not sure why there arrays are really needed. This is a lot shorter:

``````public String reverseWords(String input) {
final StringBuilder result = new StringBuilder();
final StringBuilder wordTemp = new StringBuilder();
for(int i=0; i<input.length(); i++) {
if(input.charAt(i)!=' ') {
wordTemp.insert(0, input.charAt(i));
} else {
result.append(wordTemp);
result.append(" ");
wordTemp.setLength(0);
}
}
result.append(wordTemp);
return result.toString();
}``````

• Simple two pointer solution:

``````public String reverseWords(String s) {
char[] cs = s.toCharArray();
int i = 0, j = 0;
for (j = 0; j < s.length(); j++) {
if (s.charAt(j) == ' ') {
reverse(cs, i, j - 1);
i = j + 1;
}
}
reverse(cs, i, j - 1);
return new String(cs);
}

private void reverse(char[] cs, int x, int y) {
while (x < y) {
char t = cs[x];
cs[x++] = cs[y];
cs[y--] = t;
}
}
``````

• public class Solution {
public String reverseWords(String s) {
String[] splited = s.split(" ");
for (int i = 0; i < splited.length; i++)
{
char [] yolo = splited[i].toCharArray();
char [] yolo1 = splited[i].toCharArray();
int length = yolo.length-1;
for (int j = 0; j < yolo.length; j++)
{
yolo[j] = yolo1[length];
length--;
}
splited[i] = String.valueOf(yolo);
}
String str = String.join(" ", splited);
return str;
}
}

• why is both StringBuilder and StringBuffer used in Approach #1?

• A simple more readable solution. But not very efficient as it involves marshalling and unmarshalling to and from collections.

Arrays.asList(s.split(" ")).stream().map(k -> new StringBuilder(k).reverse().append(" ")).reduce((a, b) ->a.append(b)).get().toString().trim();

• Why is complexity O(n)? Isn't it actually O(n^2) for all of the approaches? The reverse function iterates through each character in the word

• Why using StringBuffer and StringBuilder in the same solution considering one is synchronized and other not?

Anyway, I think using two index approach with an explicit reverse function would be another option. Find start and end of each word, reverse in-place and update start of the index for the next word until to the end of the string.

``````public String reverseWords(String s) {
if(s.length() == 0 || s.length() == 1) return s;
char[] str = s.toCharArray();
int start = 0;
int end = start;

while (end <= str.length - 1) {
while (end <= str.length - 1 && !Character.isWhitespace(str[end])) {
end++;
}
reverseBetween(str, start, end -1);
start = ++end;
}
return new String(str);
}

private void reverseBetween(char[] str, int start, int end) {
int s = start;
int e = end;
while(s < e) {
swap(str, s, e);
s++;
e--;
}
}

private void swap(char[] str, int first, int second) {
char tmp = str[first];
str[first] = str[second];
str[second] = tmp;
}
``````

• One liner in JavaScript :

return s.split(' ').map(word => word.split('').reverse().join('')).join(' ');

• The tricky part is that we are not able to a modify a Java `String` directly. So all the 2 above solutions use something like `StringBuilder`. Another way is to transform the `String` to a `char[]` and then it is mutable.

``````class Solution {
public String reverseWords(String s) {
final char[] c = s.toCharArray();
int left = 0, right = 0, n = c.length;
while (left < n) {
while (right < n && c[right] != ' ') {
right++;
}
reverse(c, left, right - 1);
left = ++right;
}
return String.valueOf(c);
}

private void reverse(final char[] c, final int left, final int right) {
int l = left, r = right;
while (l < r) {
final char temp = c[l];
c[l++] = c[r];
c[r--] = temp;
}
}
}
``````

• C# two pointer approach :

``````public string ReverseWords(string s) {
int left ;
left = 0;
int right ;
right = 0;
int i =0;

StringBuilder sb = new StringBuilder(s);
while(right <= sb.Length)
{
if(right == sb.Length || sb[right] == ' '  )
{
i = right;
right--;
while(left <= right)
{
char tmp = sb[right];
sb[right] = sb[left];
sb[left] = tmp;
left++;
right--;
}
left = i+1;
right = i;
}
right++;
}
return sb.ToString();
}
``````

• public class Solution {
public string ReverseWords(string s1) {

``````    if(String.IsNullOrEmpty(s1))
return s1;

int lowerBound = 0;
int upperBound = 0;

char[] s = s1.ToCharArray();

for(int i = 0; i<s.Length; i++){

if(s[i] == ' '){
upperBound = i-1;
while(lowerBound < upperBound){

char temp = s[lowerBound];
s[lowerBound] = s[upperBound];
s[upperBound] = temp;
lowerBound++;
upperBound--;
}
lowerBound = i+1;

}

}

upperBound = s1.Length -1;
while(lowerBound < upperBound){

char temp = s[lowerBound];
s[lowerBound] = s[upperBound];
s[upperBound] = temp;
lowerBound++;
upperBound--;
}

return new String(s);

}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.