My accepted Java solution


  • 75
    D
    String[] parts = s.trim().split("\\s+");
    String out = "";
    for (int i = parts.length - 1; i > 0; i--) {
        out += parts[i] + " ";
    }
    return out + parts[0];
    

    I'm splitting on the regex for one-or-more whitespace, this takes care of multiple spaces/tabs/newlines/etc in the input. Since the input could have leading/trailing whitespace, which would result in empty matches, I first trim the input string.

    Now there could be three possibilities:

    1. The input is empty: "", parts will contain [""]. The for loop is skipped and "" + "" is returned.
    2. The input contains only one part: "a", parts will contain ["a"]. The for loop is skipped and "" + "a" is returned.
    3. The input contains multiple parts: "a b c", reverse the order of all but the first part: "c b " in the for loop and return "c b " + "a".

    Obviously this is not the fastest or most memory efficient way to solve the problem, but optimizations should only be done when they are needed. Readable code is usually more important than efficient code.

    How to make it efficient?

    1. Use a StringBuilder to concatenate the string parts, instead of concatenating strings directly. This will (I assume) build something like a linked-list of string parts, and only allocate the new string when you need it, instead of on each concatenation.
    2. Iterate over the string, instead of using trim/split. Store the index of the last character in the word, when you find the first character, copy the substring to the output string.
    3. Instead of using substring, insert the word-characters directly in the StringBuilder. Assuming they're using a linked-list or tree, this could be a whole last faster.

  • 0
    I

    May be there's a problem for your solution. The result words is not as long as the source words because you change the number of the whitespace.


  • 0
    D

    If you read the description carefully, you'll find that you're supposed to replace concurrent whitespace with a single space ;-)


  • 0
    I

    Sorry, you are right.


  • 5
    A

    My solution's as follows, using StringBuilder to hold the return value instead of String:

    public String reverseWords(String s) {        
        String[] tmp = s.split("\\s");
        StringBuilder sb = new StringBuilder();
        
        for(int i = 1; i <= tmp.length; i++){
        	if(tmp[tmp.length - i].equals("")){
        		continue;
        	}
        	
        	sb.append(tmp[tmp.length - i]);
        	sb.append(" ");
        }
        
        return sb.toString().trim();
    }

  • 1
    Y

    Ha, your solution is very close to my solution. the only difference is that I moved the trim at last:)

    public String reverseWords(String s) {
        		
    	String[] ar = s.split("\\s+");
    	
    	String t ="";
    	
    	for(int i=ar.length -1; i>=0; i--)
    	{
    		t += ar[i] + " ";
    	}
    	
    	t = t.trim();
    	
    	return t;
    }
    

  • 16
    M

    Alternatively, you can use Scanner which by default will split by whitespace (and remove leading/trailing whitespace):

    public String reverseWords(String s) {
        Scanner parts = new Scanner(s);
        
        String result = "";
        
        while(parts.hasNext()){
            result = parts.next() + " " + result;
        }
        
        return result.trim();
    }
    

    This gave a 692ms solution. I also had another solution where I split the string and removed leading and trailing spaces myself. That one took only 420ms. But as daniel12 said, readable code is usually better if time/space restriction is not given.


  • 1
    W

    I reverse the whole string and reverse every single word.

    The way to filter extra space in my method is not pretty good.

    public class Solution {
        public void swap(char[] chara, int x, int nx) {
            char tmp = chara[x];
            chara[x] = chara[nx];
            chara[nx] = tmp;
        }
        
        public void reverse(char[] chara, int s, int e) {
            if (s>=e) return;
            for (int i=0;i<(e-s)/2;i++){
                swap(chara, i + s, e - i - 1);
            }
        }
        
        public String reverseWords(String s) {
            // filter extra space, make s like "word1 word2 word3"
            s = s.trim();
            char[] schar = s.toCharArray();
            StringBuilder sb = new StringBuilder();
            int former=0;
            int i=0;
            while (i<schar.length){
                if (schar[i]!=' ') { sb.append(schar[i]); i++; continue; }
                sb.append(' ');
                while(++i<schar.length && schar[i] == ' ');
            }
            schar = sb.toString().toCharArray();
    
            // do reverse
            reverse(schar, 0, schar.length);
            former=0;i=0;
            while (i<schar.length) {
                if (schar[i] != ' ') {i++;continue;}
                reverse(schar, former, i);
                while(++i<schar.length && schar[i] == ' ');
                former = i;
                
            }
            if (former!=schar.length-1) {
                reverse(schar, former, schar.length);
            }
            return new String(schar);
        }
    }

  • 0
    D

    I think this is a very good solution


  • 1
    I

    Thank you for your simple solution, but your solution cannot solve a string like "the sky is blue" with multiple white space. Here's one which can handle the case in place: O(1) space.

    public static void reverseWord(char[] s)
    {
        reverse(s, 0, s.length-1);
        int start = 0;
        int end = s.length-1;
        for(int i = 0; i < s.length; i++) //reverse each word
        {
            if(s[i] == ' ')
            {
                reverse(s, start, i-1);
                start = i+1;
            }
        }
        reverse(s, start, end); //reverse the last word
    }
    
    public static void reverse(char[] s, int start, int end)
    {
        while(start < end)
        {
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            start++;
            end--;
        }
    }
    

    Here the "void reverse()" is a helper function for "void reverseWord()".


  • 0
    K

    It wouldn't handle the case where string has just spaces.


  • 0
    A

    The solution is quite brilliant. However, it costs O(N) space.


  • 0
    H

    When the input is "", the part.length is equal to 1. So the first and the second possibility are same.


  • 0
    D

    You're right, I've simplified the code by removing the "if (parts.length > 0)" around the for-loop.


  • 0
    P

    @ico-Meng This will fail for "a b".


  • 0
    S

    Can anybody tell me what the "//s" means?:)


  • 2
    D

    "\s" is a regex class for any kind of whitespace (space, tab, newline, etc). Since Java uses "\" as an escape character in strings (e.g. for newlines: "\n"), we need to escape the escape character ;-) So it becomes "\\s". The "+" means one or more of them.


  • 0
    A

    Nice!
    The trick was using the Regex efficiently. I have used the regex in slightly different way.
    Here is my solution:-

         public String reverseWords(String s) {
    	        String[] arr = s.trim().split(" +");
    	        String s1="";
    	        for(int i = arr.length-1; i>=0; i--){
    	            	s1=s1+arr[i] + " ";
    	        }
    	        return s1.trim();
    	    }
    

    Space:- When we do s1+arr[i]+" ", a new string instance is created every single time. But the previous one is now available for garbage collection in Java. Thus Space complexity = O(w), where w is the number of words in the String.

    Time:- O(w), where w means the number of words. We are traversing the word array (arr) only once from rear to front.


  • 0
    C

    said in My accepted Java solution:

    Readable code is usually more important than efficient code.

    I like this sentence!


  • 0
    T

    No StringBuilder, no love.
    your solution immediately makes it O(n!) cuz string concatenation


Log in to reply
 

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