Reverse Words in a String


#1

Given an input string, reverse the string word by word.

Example:  

Input: "the sky is blue",
Output: "blue is sky the".

Note:

  • A word is defined as a sequence of non-space characters.
  • Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
  • You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up: For C programmers, try to solve it in-place in O(1) space.


#2

The below does two things.

  • Reverse the whole string first.
  • Copy each word to the start and reverse it. This will take care of more than one space between words.
public class Solution {
    public String reverseWords(String s) {
        if (s == null) {
            return null;
        }
        char[] str = s.toCharArray();
        
        // reverse the whole string first
        reverse(str, 0, str.length - 1);
       int index = 0;
        // here we copy over each word to the start and reverse each of them.
       for(int i=0;i<str.length;i++){
           if (str[i] != ' ') {
               // start of a new word, so we add the space
               if(index != 0){
                   str[index++] = ' ';
               }

               int j=i;
               while(j<str.length && str[j]!=' '){
                   str[index++] = str[j++];
               }
               // index-(j-i) coz we want to know how much did index move. so current position of index
               // minus how much "j" moved since it was "i"
               reverse(str, index-(j-i), index-1);
               i=j;
           }
       }
        
        // finally return the sub string from 0 to index.
        return new String(str).substring(0, index);
    }
    
    public void reverse(char[] str, int i, int j) {
        while (i < j) {
            char tem = str[i];
            str[i++] = str[j];
            str[j--] = tem;
        }
    }
}

#3

Starting from the end, adding all valid words.

public class Solution {
    public String reverseWords(String s) {
        if(s==null || s.length()==0) return "";
        StringBuilder result = new StringBuilder();
        for(int i=s.length()-1;i>=0;i--){
            if(s.charAt(i)!=' '){
                int j=i;
                while(j>=0 && s.charAt(j)!=' ') j--;
                result.append(' ');
                result.append(s.substring(j+1, i+1));
                i = j;
            }
        }
       
        return result.toString().trim();
    }
}