Monday, February 2, 2015

Reverse Words in a String II (LeetCode String)

Question: Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Could you do it in-place without allocating extra space?

Idea: Reverse twice, both in place.

Time: O(n) Space: O(1)

Code:
 public class Solution {  
   public void reverseWords(char[] s) {  
     if(s==null||s.length==0)  
       return;  
     reverse(s,0,s.length-1);  
     for(int left=0;left<s.length;left++)  
     {  
       if(s[left]!=' ')  
       {  
         int right=left;  
         while(right<s.length&&s[right]!=' ')  
           right++;  
         reverse(s,left,right-1);  
         left=right;  
       }  
     }  
   }  
   public void reverse(char[] chars, int start,int end)  
   {  
     for(int i=start,j=end;i<j;i++,j--)  
     {  
       char tmp=chars[i];  
       chars[i]=chars[j];  
       chars[j]=tmp;  
     }  
   }  
 }  

No comments:

Post a Comment