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"Solution
To solve it, we divide the input number into chunks so that each has 3 digits.
One note about this LeetCode problem is that some edge cases such as "101" is considered as "One Hundred One" instead of "One Hundred And One". So this should not be correct in real life application!
I. Java Solution
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){ String result = ""; if (num > 99){ result = map1[num / 100] + HUNDRED; } num %= 100; if(num < 20){ result += map1[num]; }else { result += map2[num/10] + map1[num%10]; } return result; } public String numberToWords(int num) { if (num == 0) return "Zero"; String result = ""; int i = 0; //check if it is thousand, million, billion while(num != 0){ if(num % 1000 != 0) result = threeDigitToWords(num % 1000) + map3[i] + result; i++; num /= 1000; } return result.trim(); } }II. Python Solution
class Solution(object): def __init__(self): self.map1 = ["", " One", " Two", " Three", " Four", " Five", " Six", " Seven", " Eight", " Nine", " Ten", " Eleven", " Twelve", " Thirteen", " Fourteen", " Fifteen", " Sixteen", " Seventeen", " Eighteen", " Nineteen" ] self.map2 = ["", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty", " Seventy", " Eighty", " Ninety" ] self.map3 = ["", " Thousand", " Million", " Billion"] self.HUNDRED = " Hundred" def threeDigitToWords(self, num): result = "" if num > 99 : result = self.map1[num / 100] + self.HUNDRED num %= 100 if num < 20: result += self.map1[num] else: result += self.map2[num/10] + self.map1[num%10] return result def numberToWords(self, num): """ :type num: int :rtype: str """ if num == 0: return "Zero" result = "" i = 0 #check if it is thousand, million, billion while num != 0: if num % 1000 != 0: result = self.threeDigitToWords(num % 1000) + self.map3[i] + result i+=1 num /= 1000 return result[1:];Appendix B: Pythonic Solution
Below is the short pythonic code.
class Solution(object): def numberToWords(self, num): """ :type num: int :rtype: str """ def make_lists(s): return [[]] + [[i] for i in s.split()] under20 = make_lists('One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \ 'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen') tens = [[]] + make_lists('Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety') thousands = make_lists("Thousand Million Billion") def threeDigitToWords(n): return (under20[n/100] + ['Hundred'] if n>99 else []) + tens[n%100/10] + (under20[n%100] if n%100 < 20 else under20[n%100%10]) def toWords(n,i): return (toWords(n/1000,i+1) if n else []) + threeDigitToWords(n%1000) + (thousands[i] if n%1000 else []) return ' '.join(toWords(num,0)) or 'Zero'
class Solution(object): def numberToWords(self, num): """ :type num: int :rtype: str Credited: LeetCode """ under20 = '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 find_words(n): if n < 20: return under20[n-1:n] if n < 100: return [tens[n/10-2]] + find_words(n%10) if n < 1000: return [under20[n/100-1]] + ['Hundred'] + find_words(n%100) for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1): if n < 1000**(p+1): return find_words(n/1000**p) + [w] + find_words(n%1000**p) return ' '.join(find_words(num)) or 'Zero'
No comments:
Post a Comment