273. Integer to English Words

  • 21.5%

https://leetcode.com/problems/integer-to-english-words/#/description

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

1
2
3
4
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"

Hint:

  1. Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.
  2. Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.
  3. There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

https://discuss.leetcode.com/topic/24112/fairly-clear-4ms-c-solution

Fairly Clear 4ms C++ solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
static string numberToWords(int n) {
if(n == 0) return "Zero";
else return int_string(n).substr(1);
}
private:
static const char * const below_20[];
static const char * const below_100[];
static string int_string(int n) {
if(n >= 1000000000) return int_string(n / 1000000000) + " Billion" + int_string(n - 1000000000 * (n / 1000000000));
else if(n >= 1000000) return int_string(n / 1000000) + " Million" + int_string(n - 1000000 * (n / 1000000));
else if(n >= 1000) return int_string(n / 1000) + " Thousand" + int_string(n - 1000 * (n / 1000));
else if(n >= 100) return int_string(n / 100) + " Hundred" + int_string(n - 100 * (n / 100));
else if(n >= 20) return string(" ") + below_100[n / 10 - 2] + int_string(n - 10 * (n / 10));
else if(n >= 1) return string(" ") + below_20[n - 1];
else return "";
}
}
};

const char * const Solution::below_20[] = {"One", "Two", "Three", "Four","Five","Six","Seven","Eight","Nine","Ten", "Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
const char * const Solution::below_100[] = {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

https://discuss.leetcode.com/topic/22949/c-solution-4ms

C++ solution 4ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//8ms

string helper(int& num){
const static char* less_ten[] =
{ "", " One", " Two", " Three", " Four", " Five", " Six", " Seven", " Eight", " Nine" };
const static char* less_twenty[] =
{ " Ten", " Eleven", " Twelve", " Thirteen", " Fourteen", " Fifteen", " Sixteen", " Seventeen", " Eighteen", " Nineteen" };
const static char* less_hundred[] =
{ "", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty", " Seventy", " Eighty", " Ninety" };

int less_thousand = num % 1000;
num /= 1000;
string s;

if (less_thousand != 0){
int hundred = less_thousand / 100;
less_thousand %= 100;
int tenth = less_thousand / 10;
int single = less_thousand % 10;

if (hundred) s = s + less_ten[hundred] + " Hundred";

if (tenth){
if (tenth == 1){
s += less_twenty[single];
return s;
}
else s += less_hundred[tenth];

}
if (single) s += less_ten[single];
}
return s;
}
string numberToWords(int num) {
const static char* unit[] =
{ "", " Thousand", " Million", " Billion", " Triliion" };

string s;
int i = 0;
while (num){
string part = helper(num);
if(i++ == 0){
s = part;
}
else if (part.size()) s = part + unit[i] + s;
}
s = s.size() ? s.substr(1) : "Zero";
return s;
}

A faster version and maybe easier to understand (4ms):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
string helper(int num){
const static char* less_ten[] =
{ "", " One", " Two", " Three", " Four", " Five", " Six", " Seven", " Eight", " Nine" };
const static char* less_twenty[] =
{ " Ten", " Eleven", " Twelve", " Thirteen", " Fourteen", " Fifteen", " Sixteen", " Seventeen", " Eighteen", " Nineteen" };
const static char* less_hundred[] =
{ "", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty", " Seventy", " Eighty", " Ninety" };

string s;

if (num != 0){
//get hundredth, tenth, and single digit
int hundred = num / 100;
num %= 100;
int tenth = num / 10;
int single = num % 10;

if (hundred) s = s + less_ten[hundred] + " Hundred";

if (tenth){
if (tenth == 1){ //special handling, choose from less_twenty based on value of single
s += less_twenty[single];
return s;
}
else s += less_hundred[tenth];

}
if (single) s += less_ten[single];
}
return s;
}
string numberToWords(int num) {
const static char* unit[] =
{ "", " Thousand", " Million", " Billion" };
int parts[4] = {0};
for(int i = 0; i < 4; ++i){
parts[i] = num % 1000;
num /= 1000;
}
string s;
for(int i = 0; i < 4; ++i){
if(parts[i] == 0) continue;
s = helper(parts[i]) + unit[i] + s;
}
s = s.size() ? s.substr(1) : "Zero";
return s;
}

https://discuss.leetcode.com/topic/22959/short-clean-c-code-with-explanation

Short clean C++ code, with explanation

Function hundredStr() produces a string from integer less than 100.

And in numberToWords() it uses a for loop to set “Thousand”,”Million”,”Billion”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
string hundredStr(int num){
vector<string> arr1={"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten",
"Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
vector<string> arr2={"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};
string ret;
ret=num%100<20?arr1[num%100]:arr2[(num%100)/10]+(num%10?" "+arr1[num%10]:"");
if(num>99)ret=arr1[num/100]+" Hundred"+(num%100?" "+ret:"");
return ret;
}
string numberToWords(int num) {
string ret;
vector<string> strarr={"Thousand","Million","Billion"};
ret=hundredStr(num%1000);
for(int i=0;i<3;i++){
num/=1000;
ret=num%1000?hundredStr(num%1000)+" "+strarr[i]+" "+ ret:ret;
}
while(ret.back()==' ')ret.pop_back();
return ret.empty()?"Zero":ret;
}
};

https://discuss.leetcode.com/topic/23061/recursive-python

Recursive Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def numberToWords(self, num):
to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
def words(n):
if n < 20:
return to19[n-1:n]
if n < 100:
return [tens[n/10-2]] + words(n%10)
if n < 1000:
return [to19[n/100-1]] + ['Hundred'] + words(n%100)
for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):
if n < 1000**(p+1):
return words(n/1000**p) + [w] + words(n%1000**p)
return ' '.join(words(num)) or 'Zero'

https://discuss.leetcode.com/topic/39814/python-clean-solution

Python Clean Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def __init__(self):
self.lessThan20 = ["","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"]
self.tens = ["","Ten","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"]
self.thousands = ["","Thousand","Million","Billion"]

def numberToWords(self, num):
if num == 0:
return "Zero"
res = ""
for i in range(len(self.thousands)):
if num % 1000 != 0:
res = self.helper(num%1000) + self.thousands[i] + " " + res
num /= 1000
return res.strip()

def helper(self, num):
if num == 0:
return ""
elif num < 20:
return self.lessThan20[num] + " "
elif num < 100:
return self.tens[num/10] + " " + self.helper(num%10)
else:
return self.lessThan20[num/100] + " Hundred " + self.helper(num%100)

8ms, 26.68%, 17 July 2016

https://discuss.leetcode.com/topic/49124/the-simplest-recursive-solution-ever-yet-efficient-enough-in-c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
private:
const vector<string> numerals{"Billion", "Million", "Thousand", "Hundred", "Ninety","Eighty", "Seventy","Sixty", "Fifty", "Forty", "Thirty", "Twenty", "Nineteen", "Eighteen", "Seventeen", "Sixteen", "Fifteen", "Fourteen", "Thirteen", "Twelve","Eleven", "Ten","Nine", "Eight", "Seven", "Six", "Five", "Four", "Three","Two", "One"};
const vector<int> units = {1000000000, 1000000, 1000, 100, 90, 80, 70, 60,50, 40,30,20,19, 18, 17, 16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
public:
string numberToWords(int num)
{
if(num == 0) return "Zero";
int i = 0;
for(; num < units[i]; ++i) ;
int upper = num/units[i];
int lower = num%units[i];
return (i<4? numberToWords(upper) + " " : "") + numerals[i] + (lower? " " + numberToWords(lower) : "");
}
};
谢谢你,可爱的朋友。