[Integer To] Integer to English Words

1. Example
PREPEND, larger, later
// check hundred, >99

// check <= 99 

// check 1000

Input:123
Output:"OneHundredTwentyThree"
Expected:"One Hundred Twenty Three"
Add space before words, like " Hundred"
non-negative, Given input is guaranteed to be less than 2^31-1

123-> "One Hundred Twenty Three"
12345->"Twelve Thousand Three hundred Forty Five"
1234567->"One Million Two Hundred Thirty Four Thousand Sixty Seven"

2. Implementation
Q1: String of unit?
A1: a strign array
Q1: how to divide a number ?
A1: > thousand, < thousand;  > million ,< million; ans 2^31-1 = 2147 48 3647 billion
> billion, < billion
Q1: Left to right or right to left?
A1: PREPEND

int i = 0;

// check if it is thousand, million, billion 

while ( num != 0) {

 if ( num%1000 != 0) 

res = threeDigitToWords( num % 1000 ) + map3[i] + res;

 i++;

 num/=1000; 

}

//NOTE :
// check hundred, >99

 if (num > 99)

 {

 res = map1[num/100] + HUNDRED; 

 } 

 num%= 100;



// check <= 99 

 if ( num < 20)

 res +=map1[num]; 

 else 

 res+= map2[num/10]+ map1[num%10];

// check 1000
if ( num%1000 != 0 )

 res = threeDigitToWords( num % 1000 ) + map3[i] + res;
String[] map3 = new String[]{""," Thousand"," Million"," Billion"}; 

// avoid digit 0
String[] map2 = new String[]{"",""," Twenty"," Thirty"," Forty"," Fifty"," Sixty"," Seventy"," Eighty"," Ninety"};

// Avoid digit 0 and 1

// Time:O(m), number of digits
public class Solution 
{



     String[] map1 = new String[] {"", " One"," Two"," Three"," Four"," Five"," Six"," Seven"," Eight"," Nine"," Ten"," Eleven"," Twelve"," Thirteen"," Fourteen"," Fifteen"," Sixteen", " Seventeen", " Eighteen"," Nineteen"};
     String[] map2 = new String[]{"",""," Twenty"," Thirty"," Forty"," Fifty"," Sixty"," Seventy"," Eighty"," Ninety"};
     String[] map3 = new String[]{""," Thousand"," Million"," Billion"};
     final String HUNDRED = " Hundred";




     public String threeDigitToWords(int num)
     {//0~999




          String res = "";




          // check hundred
          if (num > 99)
          {
               res = map1[num/100] + HUNDRED;
          }
          num%= 100;




          // check < 99
          if ( num < 20) 
               res +=map1[num];
          else
               res+= map2[num/10]+ map1[num%10];

      


          return res;



     }



     public String numberToWords(int num)
     {

          

           // validate the input
           if ( num == 0) return "Zero";
           String res = "";
            



           int i = 0;// check if it is thousand, million, billion
           while (   num !=  0)
           {
                 if ( num%1000 != 0)
                     res = threeDigitToWords(  num % 1000 ) + map3[i] + res;
                 i++;
                 num/=1000;
           }



           return res.trim();


     }
     


}

3. Similar Ones
(M) Integer to Roman