Google Code jam:Reverse Words in O(nm)

Problem

Given a list of space separated words, reverse the order of the words. Each line of text contains L letters and W words. A line will only consist of letters and space characters. There will be exactly one space character between each pair of consecutive words.

 

Input

The first line of input gives the number of cases, N.

N test cases follow. For each test case there will a line of letters and space characters indicating a list of space separated words. Spaces will not appear at the start or end of a line.

Output

For each test case, output one line containing "Case #x: " followed by the list of words in reverse order.

Limits

Small dataset

N = 5

1 ≤ L ≤ 25

Large dataset

N = 100

1 ≤ L ≤ 1000

Sample

Input                  Output 
3
this is a test         Case #1: test a is this 
foobar                 Case #2: foobar  
all your base          Case #3: base your all   

Trick: in O(nm) n is the number of input String,m is the max length of word
input: this is a test
intermediate: tset a si siht(focus here)
output: test a is this

package reversewords;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;

public class StringManager {
 private static Scanner s;
 static File f1;// This class is used for creation of files and directories,
 static File f2; // file searching, file deletion etc.
 static int cases;// total no. of cases
 private static PrintWriter pw;

 public static void main(String[] args) {
  f1 = new File("B-large-practice.in");
  f2 = new File("B-large-practice.out");
  // below code might throw anexception
  try {
   s = new Scanner(f1);
   pw = new PrintWriter(f2);
   cases = Integer.parseInt(s.nextLine());
   int num = 1;// like case #num
   while (cases != 0) {
    StringReverse sr = new StringReverse(s.nextLine());
    pw.println("Case #" + num++ + ": " + sr.reverseAll());
    cases--;
   }
   s.close();
   pw.close();
  } catch (FileNotFoundException e) {
   System.out.println("FileNotFoundException ");
  }
 }

}

package reversewords;

public class StringReverse {

 char ch[];

 public StringReverse(String str) {
  ch = str.toCharArray();

 }

 void print() {
  for (char c : ch)
   System.out.print(c);
  System.out.println();
 }

 String reverseAll() {
  reverse(0, ch.length - 1);

  for (int i = 0, j = 0; i <= ch.length; i++) {
   if (i == ch.length || ch[i] == ' ') {
    reverse(j, i - 1);
    j = i + 1;

   }

  }
  return new String(ch);

 }

 void reverse(int i, int j) {
  char temp;
  for (; i < j; i++, j--) {
   temp = ch[i];
   ch[i] = ch[j];
   ch[j] = temp;

  }

 }

}