Hard
https://leetcode.com/problems/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"
思路: recursively find answer, but mostly tricks. (545 % 100 = 45)
* Use 1000 to separate number parts. * put empty string in array for easy indexing
* Process number by dividing 1000, and helper handles from (0-999), 注意整数,word从小(右)加起, eg 5,357,545 is five million three hundred fifty seven thousand five hundred forty five
* use trim() to remove extra spaces in the end (trim can also remove start, not used here)
public class Solution { //"" is kept for index simplicity. TENS: 1st 2nd never used, keep for index simplicity 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;//ptr to thousands String words = ""; while(num>0){ if(num%1000 != 0){//avoid special case 1,000,000 else return one million thousand words = helper(num%1000) + THOUSANDS[i] + " " + words; } num /= 1000; i++; } return words.trim();//remove extra space in the end. } 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);//avid extra space by recur call }else{//100-999 return LESS_THAN_20[num/100] + " Hundred " + helper(num%100); } } }步骤:
No comments:
Post a Comment