Reverse Words in a String

Analysis:
A straight forward approach is to do with two-pass, first pass extract all the words, store in either array or stack. Second pass output.

The one pass solution uses two pointers to keep track of the start of the word and end of the word by reserve scanning.   Since substring will be used, need to check s.charAt(start - 1), then we can use s.substring(start, end) to extract word.

Solution:

 public class Solution {  
   public String reverseWords(String s) {  
     StringBuilder sb = new StringBuilder();  
     int end = s.length();  
     for (int start = s.length() - 1; start >= 0; start--) {  
       if (s.charAt(start) == ' ') {  
         end = start;    
       } else if ( start == 0 || s.charAt(start - 1) == ' ') {  
         if (sb.length() != 0) {  
           sb.append(' ');   
         }  
         sb.append(s.substring(start, end));  
       }  
     }  
     return sb.toString();  
   }  
 }