273. Integer to English Words

/*
 * @lc app=leetcode id=273 lang=cpp
 *
 * [273] Integer to English Words
 *
 * https://leetcode.com/problems/integer-to-english-words/description/
 *
 * algorithms
 * Hard (34.09%)
 * Likes:    3738
 * Dislikes: 6794
 * Total Accepted:    544.8K
 * Total Submissions: 1.6M
 * Testcase Example:  '123'
 *
 * Convert a non-negative integer num to its English words representation.
 *
 *
 * Example 1:
 *
 *
 * Input: num = 123
 * Output: "One Hundred Twenty Three"
 *
 *
 * Example 2:
 *
 *
 * Input: num = 12345
 * Output: "Twelve Thousand Three Hundred Forty Five"
 *
 *
 * Example 3:
 *
 *
 * Input: num = 1234567
 * Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty
 * Seven"
 *
 *
 *
 * Constraints:
 *
 *
 * 0 <= num <= 2^31 - 1
 *
 *
 */

// @lc code=start
class Solution {
public:
    string numberToWords(int num) {
       if (num == 0) return "Zero";

        vector<pair<int, string>> units = {
            {1000000000, "Billion"},
            {1000000, "Million"},
            {1000, "Thousand"},
            {1, ""}
        };

        string res;
        for (auto& [val, name] : units) {
            if (num >= val) {
                string segment = helper(num / val);
                res += segment + (name.empty() ? "" : " " + name) + " ";
                num %= val;
            }
        }
        while (!res.empty() && res.back() == ' ') res.pop_back();
        return res;
    }
    string helper(int num) {
        vector<string> below_20 = {
            "", "One", "Two", "Three", "Four", "Five", "Six", "Seven",
            "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen",
            "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"
        };
        vector<string> tens = {
            "", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"
        };
        string res;
        if (num < 20) {
            res = below_20[num];
        } else if (num < 100) {
            res = tens[num / 10];
            if (num % 10 != 0) {
                res += " " + helper(num % 10);
            }
            return res;
        } else {
            res = below_20[num / 100] + " Hundred";
            if (num % 100 != 0) {
                res += " " + helper(num % 100);
            }
        }
        return res;
    }
};
// @lc code=end