Wednesday, January 18, 2017

Leetcode/F家微软 -- 273. Integer to English Words (Recursion)

273. Integer to English Words (Recursion)
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