https://leetcode.com/problems/integer-to-english-words/
2. -num也会overflow; array index should be int
考虑负数
https://www.bbsmax.com/A/D854p0w5Eg/
https://leetcode.com/problems/integer-to-english-words/discuss/70627/Short-clean-Java-solution
X. Iterative
https://leetcode.com/problems/integer-to-english-words/discuss/70625/My-clean-Java-solution-very-easy-to-understand
http://likesky3.iteye.com/blog/2240465
class Solution(object): 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'
def numberToWords(self, num): lv1 = "Zero One Two Three Four Five Six Seven Eight Nine Ten \ Eleven Twelve Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen".split() lv2 = "Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety".split() lv3 = "Hundred" lv4 = "Thousand Million Billion".split() words, digits = [], 0 while num: token, num = num % 1000, num / 1000 word = '' if token > 99: word += lv1[token / 100] + ' ' + lv3 + ' ' token %= 100 if token > 19: word += lv2[token / 10 - 2] + ' ' token %= 10 if token > 0: word += lv1[token] + ' ' word = word.strip() if word: word += ' ' + lv4[digits - 1] if digits else '' words += word, digits += 1 return ' '.join(words[::-1]) or 'Zero'
Read full article from LIKE CODING: LeetCode [273] Integer to English Words
Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
Example 1:
Input: 123 Output: "One Hundred Twenty Three"
Example 2:
Input: 12345 Output: "Twelve Thousand Three Hundred Forty Five"
Example 3:
Input: 1234567 Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
Example 4:
Input: 1234567891 Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/273_Integer_to_English_Words.java
2. -num也会overflow; array index should be int
考虑负数
final static int[] POW10 = {1, 10, 100, 1000, 0, 0, 1000000, 0, 0, 1000000000};
final static String[] ONES = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
final static String[] TENS = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
public String numberToWords(int num) {
if (num == 0) return "Zero";
boolean negative = false;
long n = num;
if (num < 0) {
negative = true;
n = -n;
}
String rtn = helper(n);
return negative ? "Negative " + rtn : rtn;
}
private String helper(long n) {
String rtn = "";
if (n < 20) rtn = ONES[(int)n];
else if (n < POW10[2]) rtn = TENS[(int)n / POW10[1]] + " " + ONES[(int)n % POW10[1]];
else if (n < POW10[3]) rtn = ONES[(int)n / POW10[2]] + " Hundred " + helper(n % POW10[2]);
else if (n < POW10[6]) rtn = helper(n / POW10[3]) + " Thousand " + helper(n % POW10[3]);
else if (n < POW10[9]) rtn = helper(n / POW10[6]) + " Million " + helper(n % POW10[6]);
else rtn = helper(n / POW10[9]) + " Billion " + helper(n % POW10[9]);
return rtn.trim();
}
final static String[] HUNDS = {"Hundred", "Thousand", "Million", "Billion"};
final static String[] ONES = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
final static String[] TENS = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
public String numberToWords(int num) {
if (num == 0) return "Zero";
boolean negative = false;
long n = num;
if (num < 0) {
negative = true;
n = -n;
}
List<String> ans = new ArrayList<String>();
int cnt = -1;
while (n > 0) {
int hunds = (int)(n % 1000);
n /= 1000; ++ cnt;
if (hunds == 0) continue;
if (cnt > 0) ans.add(HUNDS[cnt]);
int tens = hunds % 100;
if (tens > 0 && tens < 20) ans.add(ONES[tens]);
else {
if (tens % 10 > 0) ans.add(ONES[tens % 10]);
if (tens / 10 > 0) ans.add(TENS[tens / 10]);
}
if (hunds / 100 > 0) {
ans.add(HUNDS[0]);
ans.add(ONES[hunds / 100]);
}
}
if (negative) ans.add("Negative");
Collections.reverse(ans);
return String.join(" ", ans);
}
http://blog.welkinlan.com/2015/09/29/integer-to-english-words-leetcode-java/
public class Solution {
private final String[] lessThan20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private final String[] tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
private final String[] thousands = {"", "Thousand", "Million", "Billion"};
public String numberToWords(int num) {
if (num == 0) {
return "Zero";
}
String result = "";
int i = 0;
while (num > 0) {
if (num % 1000 != 0) {
result = helper(num % 1000) + thousands[i] + " " + result;
}
num /= 1000;
i++;
}
return result.trim();
}
private String helper(int num) {
if (num == 0) {
return "";
} else if (num < 20) {
return lessThan20[num] + " ";
} else if (num < 100) {
return tens[num / 10] + " " + helper(num % 10);
} else {
return lessThan20[num / 100] + " Hundred " + helper(num % 100);
}
}
}
https://www.bbsmax.com/A/D854p0w5Eg/
https://leetcode.com/problems/integer-to-english-words/discuss/70627/Short-clean-Java-solution
private final String[] belowTen = new String[] {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
private final String[] belowTwenty = new String[] {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private final String[] belowHundred = new String[] {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
public String numberToWords(int num) {
if (num == 0) return "Zero";
return helper(num);
}
private String helper(int num) {
String result = new String();
if (num < 10) result = belowTen[num];
else if (num < 20) result = belowTwenty[num -10];
else if (num < 100) result = belowHundred[num/10] + " " + helper(num % 10);
else if (num < 1000) result = helper(num/100) + " Hundred " + helper(num % 100);
else if (num < 1000000) result = helper(num/1000) + " Thousand " + helper(num % 1000);
else if (num < 1000000000) result = helper(num/1000000) + " Million " + helper(num % 1000000);
else result = helper(num/1000000000) + " Billion " + helper(num % 1000000000);
return result.trim();
}
X. Iterative
https://leetcode.com/problems/integer-to-english-words/discuss/70625/My-clean-Java-solution-very-easy-to-understand
private final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
private final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};
public String numberToWords(int num) {
if (num == 0) return "Zero";
int i = 0;
String words = "";
while (num > 0) {
if (num % 1000 != 0)
words = helper(num % 1000) +THOUSANDS[i] + " " + words;
num /= 1000;
i++;
}
return words.trim();
}
private String helper(int num) {
if (num == 0)
return "";
else if (num < 20)
return LESS_THAN_20[num] + " ";
else if (num < 100)
return TENS[num / 10] + " " + helper(num % 10);
else
return LESS_THAN_20[num / 100] + " Hundred " + helper(num % 100);
}
String[] digit = {"", " One", " Two", " Three", " Four", " Five",
" Six", " Seven", " Eight", " Nine"};
String[] tenDigit = {" Ten", " Eleven", " Twelve", " Thirteen", " Fourteen", " Fifteen",
" Sixteen", " Seventeen", " Eighteen", " Nineteen"};
String[] tenMutipleDigit = {"", "", " Twenty", " Thirty", " Forty", " Fifty",
" Sixty", " Seventy", " Eighty", " Ninety"};
public String numberToWords(int num) {
String[] bigs = new String[]{" Thousand", " Million", " Billion"};
StringBuilder sb = new StringBuilder();
int i = 0;
sb.append(convertToWords(num % 1000));
num /= 1000; // no need to first preprocess
while (num > 0) {
if (num % 1000 != 0) {
sb.insert(0, convertToWords(num % 1000) + bigs[i]);
}
i++;
num /= 1000;
}
return sb.length() == 0 ? "Zero" : sb.toString().trim();
}
public String convertToWords(int num) { //rename to like: threeDigitToWords
StringBuilder sb = new StringBuilder();
if (num >= 100) {
sb.append(digit[num / 100]).append(" Hundred");
num %= 100;
}
if (num > 9 && num < 20) {
sb.append(tenDigit[num - 10]);
} else {
if (num >= 20) {
sb.append(tenMutipleDigit[num / 10]);
num %= 10;
}
sb.append(digit[num]);
}
return sb.toString();
}
string translate(vector<string> &ones,vector<string> &oneTens,vector<string> &tens,vector<string> &ends,
int
nums,string end) {
string rt =
""
;
if
(nums >= 100) {
rt += ones[nums / 100 - 1] +
" Hundred"
;
nums %= 100;
}
if
(nums >= 10) {
if
(rt !=
""
) rt +=
" "
;
if
(nums <= 19) {
rt += oneTens[nums % 10];
return
rt + end;
}
rt += tens[nums / 10 - 2];
nums %= 10;
}
if
(nums >= 1) {
if
(rt !=
""
) rt +=
" "
;
rt += ones[nums - 1];
}
return
rt + end;
}
string numberToWords(
int
num) {
if
(num == 0)
return
"Zero"
;
vector<string> ones = {
"One"
,
"Two"
,
"Three"
,
"Four"
,
"Five"
,
"Six"
,
"Seven"
,
"Eight"
,
"Nine"
};
vector<string> oneTens = {
"Ten"
,
"Eleven"
,
"Twelve"
,
"Thirteen"
,
"Fourteen"
,
"Fifteen"
,
"Sixteen"
,
"Seventeen"
,
"Eighteen"
,
"Nineteen"
};
vector<string> tens = {
"Twenty"
,
"Thirty"
,
"Forty"
,
"Fifty"
,
"Sixty"
,
"Seventy"
,
"Eighty"
,
"Ninety"
};
vector<string> ends = {
" Billion"
,
" Million"
,
" Thousand"
,
""
};
string rt =
""
;
int
temp = 0, endI = 0,bill = 1000000000;
while
(num > 0) {
if
(num / bill > 0) {
if
(rt !=
""
) rt +=
" "
;
rt += translate(ones,oneTens,tens,ends,num / bill,ends[endI]);
}
num %= bill;
bill /= 1000;
endI++;
}
return
rt;
}
class Solution {
unordered_map<int, string> hash;
public:
Solution(){
hash[0] =
"Zero"
;
hash[1] =
"One"
;
hash[2] =
"Two"
;
hash[3] =
"Three"
;
hash[4] =
"Four"
;
hash[5] =
"Five"
;
hash[6] =
"Six"
;
hash[7] =
"Seven"
;
hash[8] =
"Eight"
;
hash[9] =
"Nine"
;
hash[10] =
"Ten"
;
hash[11] =
"Eleven"
;
hash[12] =
"Twelve"
;
hash[13] =
"Thirteen"
;
hash[14] =
"Fourteen"
;
hash[15] =
"Fifteen"
;
hash[16] =
"Sixteen"
;
hash[17] =
"Seventeen"
;
hash[18] =
"Eighteen"
;
hash[19] =
"Nineteen"
;
hash[20] =
"Twenty"
;
hash[30] =
"Thirty"
;
hash[40] =
"Forty"
;
hash[50] =
"Fifty"
;
hash[60] =
"Sixty"
;
hash[70] =
"Seventy"
;
hash[80] =
"Eighty"
;
hash[90] =
"Ninety"
;
}
string numberToWordsLessThousand(int num){
if
(!num)
return
hash[num];
string s;
if
(num/100) s += hash[num/100] +
" Hundred"
;
num = num%100;
if
(num>=20){
if
(!s.empty()) s = s+
" "
;
s += hash[num/10*10];
num = num%10;
}
if
(num){
if
(!s.empty()) s = s+
" "
;
s += hash[num];
}
return
s;
}
string numberToWords(int num) {
if
(!num)
return
hash[num];
string s;
if
(num>=BILLION){
int nb = num/BILLION;
s += numberToWordsLessThousand(nb) +
" Billion"
;
num = num%BILLION;
}
if
(num>=MILLION){
if
(!s.empty()) s = s+
" "
;
int nm = num/MILLION;
s += numberToWordsLessThousand(nm) +
" Million"
;
num = num%MILLION;
}
if
(num>=THOUSAND){
if
(!s.empty()) s = s+
" "
;
int nt = num/THOUSAND;
s += numberToWordsLessThousand(nt) +
" Thousand"
;
num = num%THOUSAND;
}
if
(num){
if
(!s.empty()) s = s+
" "
;
s += numberToWordsLessThousand(num);
}
return
s;
}
};
- public String numberToWords(int num) {
- if (num == 0) return "Zero";
- StringBuilder result = new StringBuilder();
- boolean hasBillion = false;
- boolean hasMillion = false;
- boolean hasThousand = false;
- if (num >= 1000000000) {
- hasBillion = true;
- result.append(digits[num / 1000000000]).append(' ').append("Billion").append(' ');
- num %= 1000000000;
- }
- if (num >= 1000000) {
- hasMillion = true;
- result.append(readALessThousandNum(String.valueOf(num / 1000000), false)).append(' ').append("Million").append(' ');
- num %= 1000000;
- } /*else if (hasBillion && num > 0) {
- result.append("and").append(' ');
- }*/
- if (num >= 1000) {
- hasThousand = true;
- result.append(readALessThousandNum(String.valueOf(num / 1000), false)).append(' ').append("Thousand").append(' ');
- num %= 1000;
- } /*else if (hasMillion && num > 0) {
- result.append("and").append(' ');
- }*/
- result.append(readALessThousandNum(String.valueOf(num), hasThousand));
- return result.toString().trim();
- }
- private String[] digits = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
- private String[] tenx = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen",
- "Fifteen", "Sixteen", "Seventeen","Eighteen", "Nineteen"
- };
- private String[] tens = {"","","Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
- public String readALessThousandNum(String num, boolean hasThousand) {
- if (num.length() == 1)
- num = "00" + num;
- else if (num.length() == 2)
- num = "0" + num;
- StringBuilder result = new StringBuilder();
- boolean hasHundred = false;
- if (num.charAt(0) != '0') {
- hasHundred = true;
- result.append(digits[num.charAt(0) - '0']).append(' ').append("Hundred").append(' ');
- } /*else if (hasThousand && (num.charAt(1) != '0'|| num.charAt(0) != '0')) {
- result.append("and");
- }*/
- if (num.charAt(1) == '0' && num.charAt(2) != '0') {
- // if ((hasHundred || hasThousand))
- // result.append("and").append(' ');
- result.append(digits[num.charAt(2) - '0']).append(' ');
- } else if (num.charAt(1) == '1') {
- // if (hasHundred || hasThousand)
- // result.append("and").append(' ');
- result.append(tenx[num.charAt(2) - '0']).append(' ');
- } else {
- result.append(tens[num.charAt(1) - '0']).append(' ');
- if (num.charAt(2) != '0')
- result.append(digits[num.charAt(2) - '0']).append(' ');
- }
- return result.toString().trim();
- }
class Solution(object): 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'
def numberToWords(self, num): lv1 = "Zero One Two Three Four Five Six Seven Eight Nine Ten \ Eleven Twelve Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen".split() lv2 = "Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety".split() lv3 = "Hundred" lv4 = "Thousand Million Billion".split() words, digits = [], 0 while num: token, num = num % 1000, num / 1000 word = '' if token > 99: word += lv1[token / 100] + ' ' + lv3 + ' ' token %= 100 if token > 19: word += lv2[token / 10 - 2] + ' ' token %= 10 if token > 0: word += lv1[token] + ' ' word = word.strip() if word: word += ' ' + lv4[digits - 1] if digits else '' words += word, digits += 1 return ' '.join(words[::-1]) or 'Zero'
Read full article from LIKE CODING: LeetCode [273] Integer to English Words