Friday, March 28, 2014

Reverse Words in a String

Given an input string, reverse the string word by word. For example, Given s = "the sky is blue", return "blue is sky the".
Solution 1: straight forward
public class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" +");
  
        int i = words.length-1;
  
        while(i >= 0 && words[i].equals("")) i--;
        if (i < 0) return "";
  
        String result = words[i--];
        while(i >= 0) {
         if(!words[i].equals(""))
             result += " " + words[i];
         i--;
        }
        return result;
    }
}
Solution 2: space efficient
public class Solution {
    public String reverseWords(String s) {
        if(s.equals("")) return "";
  
        StringBuffer sb = new StringBuffer(s);
  
        while (sb.charAt(0) == ' ') {
         sb.deleteCharAt(0);
         if(sb.length() == 0) return "";
        }
  
        int i = 1;
        while (i < sb.length()) {
         if (sb.charAt(i-1) == ' ' && sb.charAt(i) == ' ') 
          sb.deleteCharAt(i);
         else 
          i++;
        }
  
        if (sb.charAt(sb.length() - 1) == ' ')
         sb.deleteCharAt(sb.length() - 1);
  
        swapString(sb, 0, sb.length()-1);
  
        int start = 0;
        for(int j = 0; j < sb.length(); j++) {
         if (sb.charAt(j) == ' ') {
          swapString(sb, start, j-1);
          start = j+1;
         }
        }
  
        swapString(sb, start, sb.length()-1);
  
        return sb.toString();
    }
    
    public void swapString (StringBuffer sb, int start, int end) {
        while(start < end) {
         char temp = sb.charAt(start);
         sb.setCharAt(start, sb.charAt(end));
         sb.setCharAt(end, temp);
         start++;
         end--;
        }
    }
}

No comments:

Post a Comment