[Leetcode]07/06 [String] Reverse Words in a String

/* Recursive NOTE null vs "" "" is an actual string, you can still invoke methods or functions on it like a.length() a.substring(0, 1) null, like b, Java would throw a NullPointerException if you tried invoking, say b.length() http://stackoverflow.com/questions/4802015/difference-between-null-and-java-string Mrthod1: Time:O(n), Sapce:O(n) Logic: Split and keep appending inside 1. split by space to get each word - iterate thru string when ' ' is met, record the word and skip ' ' 2. append getting word in the end Ex. the sky is blue => "sky is blue" + "the" => "is blue" + "sky " + "the" => "blue" + "is " + "sky "+"the" => "" + "blue" + "is " + "sky "+"the" NOTE: return helper(s,index).append(cur); return helper(s,index).append(cur).append(' '); Method2: (Iterative) Two poitners Time:O(n), SpacE:O(n) Logic: 先反转整体，再反转局部 1. "the sky is blue" => "eulb si yks eht" O(n) 2. "eulb si yks eht" => "blue is sky the" O(n) NOTE: s = s.trim(); It returns a copy of this string with leading and trailing white space removed // skip one of double spaces if ( i != s.length() -1 && s.charAt(i)== ' ' && s.charAt(i)==s.charAt(i+1) ) { continue; } */

public class Solution {
    public String reverseWords(String s) {
      /* Method1:
      s = s.trim();
      return helper(s,0).toString();
      */
      
      
      /* Method2:*/
      if ( s == null  )
      {
          return null;
      }
      if ( s.length() == 0 )
      {
          return "";
      }
      s = s.trim();
      // 1. reverse entire string from the last character
      StringBuilder res = new StringBuilder();
      for (  int i = s.length()-1; i >=0 ; i--  )
      {
          // skip one of double spaces
          if ( i != s.length() -1 && s.charAt(i)== ' ' && s.charAt(i)==s.charAt(i+1) )
          {
              continue;
          }
          res.append(s.charAt(i));
      }
      // 2. reverse each word, scan twice: 
      // one for length and one for reverse
      int left = 0;
      int right = 0;
      while ( right < res.length()  )
      {
          // 1. get the end index of each word
          while( right < res.length() && res.charAt(right) != ' ' )
          {
            right++;    
          }
          int next = right + 1; // right after ' '
          right--;
          // 2. two poitners for each word, 
          // one point to start and the other point the end
          while(  left < right ) 
          {
              // 3. swap
              char temp = res.charAt(left);
              res.setCharAt( left++, res.charAt(right) );
              res.setCharAt( right--, temp );
          }
          // 4. reset the start for two poitners
          left = next;
          right = next;
      }
      return res.toString();
    }
    
    // Method1:
    private StringBuilder helper( String s, int index )
    {
        // Base case
        if (  index >= s.length() )
        {
            return new StringBuilder();
        }
        // 1. append not ' ' 
        StringBuilder cur = new StringBuilder();
        int lastIndex = index;
        while ( index < s.length() && s.charAt(index) != ' ' )
        {
            cur.append( s.charAt(index++) );
        }
        // 2. remove ' '
        while ( index < s.length() && s.charAt(index) == ' ' )
        {
            index++;
        }
        
        // 3. first word append to the end
        if (lastIndex == 0 )
        {
            return helper(s,index).append(cur);
        }
        // 4. not the first word
        return helper(s,index).append(cur).append(' ');
    }
}