leetCode Question: Integer to English Words

Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

For example,

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

Analysis:

This problem is not difficult but should pay more attention for the corner cases.

General idea is to:

• Split the nums every 3 digits.
• For every 3 digits, write a function to represent into string format
• Between every 3 digits, add the correct "spliter", e.g., thousand, million, etc.
• Take care of the zeros

Please look at the Python code shown below, it should be clear enough for understanding the whole process.

Code (C++):

class Solution {

public:

string numberThreeDigits(int num, string name_1_9[], string name_10_19[], string name_20_90[]){

string res = "";

if (num / 100 > 0){ res += name_1_9[(num/100)] + " Hundred ";}

num = num % 100;

if (num / 10 > 1) {

res += name_20_90[num/10 - 2] + " ";

num = num%10;

if (num >= 1 ){res += name_1_9[num] + " ";}

} else if (num/10 == 1){

num = num% 10;

res += name_10_19[num] + " ";

} else if (num >= 1 ){

res += name_1_9[num] + " ";

}

return res;

}

string numberToWords(int num){

string name_1_9[] = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven","Eight","Nine"};

string name_10_19[] = {"Ten", "Eleven", "Twelve","Thirteen","Fourteen", "Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};

string name_20_90[] = {"Twenty", "Thirty", "Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};

string name_scale[] = {"","Thousand", "Million","Billion"};

vector<int>nums;

while (num/1000 >0){

nums.push_back(num%1000);

num = num/1000;

}

nums.push_back(num);

string res = "";

for (int i=0;i<nums.size();++i){

string tmp = numberThreeDigits(nums[i], name_1_9, name_10_19, name_20_90);

if (tmp != ""){

res = tmp + name_scale[i] + " " + res;

}else if (nums.size()==1){

res = "Zero";

}

}

int sp_pos = res.size()-1;

while (res[sp_pos] == ' '){

sp_pos--;

}

return res.substr(0,sp_pos+1);

}

};

Code (Python):

class Solution(object):

name_1_9 = ["Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven","Eight","Nine"]

name_10_19 = ["Ten", "Eleven", "Twelve","Thirteen","Fourteen", "Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"]

name_20_90 = ["Twenty", "Thirty", "Forty","Fifty","Sixty","Seventy","Eighty","Ninety"]

name_scale = ["","Thousand", "Million","Billion"]

def numberThreeDigits(self, num):

res = ""

if num / 100 > 0:

res += self.name_1_9[(num/100)] + " Hundred "

num = num % 100

if num / 10 > 1:

res += self.name_20_90[num/10 - 2] + " "

num = num%10

if num >= 1:

res += self.name_1_9[num] + " "

elif num/10 == 1:

num = num % 10

res += self.name_10_19[num] + " "

elif num >= 1:

res += self.name_1_9[num] + " "

return res

def numberToWords(self, num):

"""

:type num: int

:rtype: str

"""

nums = []

while num/1000 >0:

nums.append(num%1000)

num = num/1000

nums.append(num)

res = ""

for i in range(len(nums)):

tmp = self.numberThreeDigits(nums[i])

if tmp != "":

res = tmp + self.name_scale[i] + " " + res

elif len(nums)==1:

res = "Zero"

return res.rstrip()