给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
$number_hash = {
    "2" => ["a", "b", "c"],
    "3" => ["d", "e", "f"],
    "4" => ["g", "h", "i"],
    "5" => ["j","k","l"],
    "6" => ["m", "n", "o"],
    "7" => ["p", "q", "r", "s"],
    "8" => ["t", "u", "v"],
    "9" => ["w","x","y","z"]
}

# @param {String} digits
# @return {String[]}
def letter_combinations(digits)
    return [] if digits.length == 0
    result = []
    dm "", digits, result
    result
end

def dm combination, rest_numbers, result
    if rest_numbers.length == 0
        result << combination
        combination = ""
    else
        head = rest_numbers[0]
        $number_hash[head].each do |letter|
            _combination = combination
            _combination += letter
            dm _combination, rest_numbers[1..-1], result
        end
    end
end