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


Log in to reply
 

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