<p>Convert a non-negative integer <code>num</code> to its English words representation.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = 123
<strong>Output:</strong> &quot;One Hundred Twenty Three&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = 12345
<strong>Output:</strong> &quot;Twelve Thousand Three Hundred Forty Five&quot;
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = 1234567
<strong>Output:</strong> &quot;One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= num &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution {
    string oneDigit(int a0) {
        const vector<string> result{
            "", "One", "Two", "Three", "Four", "Five",
            "Six", "Seven", "Eight", "Nine"
        };

        return result[a0];
    }

    string twoDigit(int a1, int a0) {
        const vector<string> tens{
            "Twenty", "Thirty", "Forty", "Fifty",
            "Sixty", "Seventy", "Eighty", "Ninety"
        };

        const vector<string> teens{
            "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen",
            "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"
        };

        if (a1 == 0) {
            return oneDigit(a0);
        } else if (a1 == 1) {
            return teens[a0];
        } else {
            return join(tens[a1-2], oneDigit(a0));
        }
    }

    string threeDigit(int a2, int a1, int a0) {
        if (a2 == 0) {
            return twoDigit(a1, a0);
        } else {
            return join(join(oneDigit(a2), "Hundred"), twoDigit(a1, a0));
        }
    }

    string join(const string& lhs, const string& rhs) {
        if (lhs.empty()) {
            return rhs;
        } else if (rhs.empty()) {
            return lhs;
        } else {
            return lhs + " " + rhs;
        }
    }

public:
    string numberToWords(int num) {
        string result;
        const vector<string> suffixes{
            "", "Thousand", "Million", "Billion", "Trillion"
        };
        int suffixIndex = 0;

        if (num == 0) {
            return "Zero";
        }

        while (num) {
            int k = num % 1000;

            if (k > 0) {
                int a2 = k/100, a1 = (k%100)/10, a0 = k%10;
                result = join(
                        join(threeDigit(a2,a1,a0), suffixes[suffixIndex]),
                        result);
            }
            num /= 1000;
            suffixIndex++;
        }

        return result;
    }
};
13000