[LeetCode]Integer to English Words

首先我们要明确是如何用word来表示整数，我们可以看出来，英文中是三位数为单位的，从thousand -> million -> billion，三位数就是按照普通的处理三位数来。比如 1234567，我们先处理567 -> Five Hundred Sixty Seven，之后处理234 -> Two Hundred Four 并且 append Thousand，随后处理1 -> One 并且append Million。我们按照这个思路来处理就可以。时间复杂度O(n)，代码如下：

	class Solution {
	public:
	string numberToWords(int num) {
	//handle zero
	if(!num)return "Zero";
	//strings we need
	const vector<string> thousands = {"Thousand", "Million", "Billion"};
	string hundred = "Hundred";
	const vector<string> tens = {"Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
	const vector<string> ones = {"One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
	string res = "";
	//counting comma to keep track of thousands, 1,234,567
	int commas = 0;
	while(num)
	{
	string curr = "";
	//process every three digits
	int currNum = num % 1000;
	num /= 1000;
	//if zero, we do nothing, for example, 3,000
	if(!currNum);
	//hundreds, for example, 800
	else if(!(currNum % 100))curr = ones[currNum/ 100 - 1] + " " + hundred;
	//tens, for example, 660, 50
	else if(!(currNum % 10))curr = currNum / 100? ones[currNum / 100 - 1] + " " + hundred + " " + tens[(currNum % 100) / 10 - 1]: tens[(currNum % 100) / 10 - 1];
	else//345, 59, 7
	{
	string first = currNum / 100? ones[currNum / 100 - 1] + " " + hundred: "";
	string second = currNum / 10? (currNum % 100 < 20? ones[currNum % 100 - 1]: tens[(currNum % 100) / 10 - 1] + " " + ones[currNum % 10 - 1]): ones[currNum % 10 - 1];
	curr = first.empty()? second: first + " " + second;
	}
	if(curr.size())res = commas? curr + " " + thousands[commas - 1] + " " + res: curr + " " + res;
	++commas;
	if(res.back() == ' ')res.pop_back();
	}
	return res;
	}
	};

view raw Integer to English Words.cpp hosted with ❤ by GitHub

处理三位数的时候，可以按照我们这样处理。也可以用递归的思路来，递归的思路可以参考这里。