import java.lang.StringBuilder

// https://leetcode.com/problems/letter-combinations-of-a-phone-number
fun letterCombinations(digits: String): List<String> {
    val combinations = mutableListOf<String>()
    val digitToChars = mapOf(
        '2' to charArrayOf('a', 'b', 'c'),
        '3' to charArrayOf('d', 'e', 'f'),
        '4' to charArrayOf('g', 'h', 'i'),
        '5' to charArrayOf('j', 'k', 'l'),
        '6' to charArrayOf('m', 'n', 'o'),
        '7' to charArrayOf('p', 'q', 'r', 's'),
        '8' to charArrayOf('t', 'u', 'v'),
        '9' to charArrayOf('w', 'x', 'y', 'z')
    )
    if (digits.isNotEmpty()) {
        buildCombinations(digits, 0, StringBuilder(), combinations, digitToChars)
    }
    return combinations
}

private fun buildCombinations(
    digits: String,
    index: Int,
    combination: StringBuilder,
    combinations: MutableList<String>,
    digitToChars: Map<Char, CharArray>
) {
    if (index == digits.length) {
        combinations.add(combination.toString())
        return
    }
    for (char in digitToChars.getValue(digits[index])) {
        combination.append(char)
        buildCombinations(digits, index + 1, combination, combinations, digitToChars)
        combination.setLength(combination.length - 1)
    }
}
