package com.fishercoder.solutions;

/**
 * 186. Reverse Words in a String II

 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?
 */
public class _186 {
  public static class Solution1 {
    public void reverseWords(char[] s) {
      // Three steps to reverse
      // 1, reverse the whole sentence
      reverse(s, 0, s.length - 1);
      // 2, reverse each word
      int start = 0;
      for (int i = 0; i < s.length; i++) {
        if (s[i] == ' ') {
          reverse(s, start, i - 1);
          start = i + 1;
        }
      }
      // 3, reverse the last word, if there is only one word this will solve the corner case
      reverse(s, start, s.length - 1);
    }

    private void reverse(char[] s, int start, int end) {
      while (start < end) {
        char temp = s[start];
        s[start++] = s[end];
        s[end--] = temp;
      }
    }
  }

}

@@ -33,416 +33,8 @@
 s;%0A%0A
-/**%0A * 186. Reverse Words in a String II%0A%0A Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.%0A%0A The input string does not contain leading or trailing spaces and the words are always separated by a single space.%0A%0A For example,%0A Given s = %22the sky is blue%22,%0A return %22blue is sky the%22.%0A%0A Could you do it in-place without allocating extra space?%0A */%0A
 publ
@@ -51,16 +51,18 @@
 186 %7B%0A  
+ 
+ 
 public s
@@ -85,16 +85,20 @@
 tion1 %7B%0A
+    
     publ
@@ -136,16 +136,22 @@
 %7B%0A      
+     
+ 
 // Three
@@ -168,16 +168,22 @@
 reverse%0A
+      
       //
@@ -211,32 +211,38 @@
  sentence%0A      
+   
+   
 reverse(s, 0, s.
@@ -250,24 +250,30 @@
 ength - 1);%0A
+      
       // 2, 
@@ -296,16 +296,22 @@
 d%0A      
+ 
+     
 int star
@@ -323,16 +323,22 @@
 ;%0A      
+     
+ 
 for (int
@@ -362,24 +362,32 @@
 gth; i++) %7B%0A
+        
         if (
@@ -403,32 +403,42 @@
  ') %7B%0A          
+ 
+         
 reverse(s, start
@@ -443,24 +443,34 @@
 rt, i - 1);%0A
+          
           st
@@ -490,24 +490,46 @@
         
+ 
+       %7D%0A            
 %7D%0A      
 %7D%0A      
@@ -516,26 +516,24 @@
     %7D%0A      
-%7D%0A
       // 3, 
@@ -615,24 +615,30 @@
  case%0A      
+ 
+     
 reverse(s, s
@@ -654,24 +654,28 @@
 ength - 1);%0A
+    
     %7D%0A%0A    p
@@ -673,16 +673,20 @@
  %7D%0A%0A    
+ 
+   
 private 
@@ -726,24 +726,30 @@
  int end) %7B%0A
+      
       while 
@@ -772,16 +772,24 @@
         
+ 
+       
 char tem
@@ -810,16 +810,24 @@
         
+   
+     
 s%5Bstart+
@@ -847,16 +847,24 @@
         
+     
+   
 s%5Bend--%5D
@@ -872,16 +872,22 @@
 = temp;%0A
+      
       %7D%0A
@@ -890,17 +890,744 @@
   %7D%0A    
+ 
-%7D%0A
+   %7D%0A    %7D%0A%0A    public static class Solution2 %7B%0A        public void reverseWords(char%5B%5D s) %7B%0A            reverse(s, 0, s.length);%0A            for (int i = 0; i %3C s.length; i++) %7B%0A                int start = i;%0A                while (i %3C s.length && s%5Bi%5D != ' ') %7B%0A                    i++;%0A                %7D%0A                reverse(s, start, i);%0A            %7D%0A        %7D%0A%0A        private void reverse(char%5B%5D chars, int start, int end) %7B%0A            int left = start;%0A            int right = end - 1;%0A            while (left %3C right) %7B%0A                char tmp = chars%5Bleft%5D;%0A                chars%5Bleft%5D = chars%5Bright%5D;%0A                chars%5Bright%5D = tmp;%0A                left++;%0A                right--;%0A            %7D%0A        %7D%0A  
   %7D%0A%0A%7D%0A

add a solution for 186