Reverse words in a string


  • 0

    Click here to see the full article post


  • 0

    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.


  • 0

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


  • 0
    K

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


  • 0
    J

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

    }

  • 0
    S

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


  • 0
    F

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


  • 0
    R

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


  • 0

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


  • 0
    A

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

  • 0
    N

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

  • 0
    J

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


  • 0
    C

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


  • 0
    L

    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();


  • 0
    C

    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


  • 0
    B

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

Log in to reply
 

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