letterCombos

import (
    "fmt"
    "strconv"
)

func letterCombinations(digits string) []string {

    var combinations []string
    var digitsArray []int
    // null case
    if len(digits) == 0 {
        return combinations
    }

    // recursive base case
    if len(digits) == 1 {
        digit, err := strconv.Atoi(string(digits[0]))
        if err != nil {
            fmt.Println("couldn't parse input")
        }
        return buildCombos(digit)
    }

    // parse input
    for i := 0; i < len(digits); i++ {
        digit, err := strconv.Atoi(string(digits[i]))
        if err != nil {
            fmt.Println("couldn't parse input")
        }
        digitsArray = append(digitsArray, digit)
    }

    // recursive case - builds up combinations of letters
    firstLetters := buildCombos(digitsArray[0])
    nextLetters := letterCombinations(digits[1:])
    for j := 0; j < len(firstLetters); j++ {
        for k := 0; k < len(nextLetters); k++ {
            appendThis := firstLetters[j] + nextLetters[k]
            combinations = append(combinations, appendThis) 
        }
    }
    return combinations
}

// stores and returns the possible letter values for each numeric key
func buildCombos(digit int) []string{
    phone := map[int][]string {
        0: []string{" "},
        1: []string{""},
        2: []string{"a", "b", "c"},
        3: []string{"d", "e", "f"},
        4: []string{"g", "h", "i"},
        5: []string{"j", "k", "l"},
        6: []string{"m", "n", "o"},
        7: []string{"p", "q", "r", "s"},
        8: []string{"t", "u", "v"},
        9: []string{"w", "x", "y", "z"}}
    return phone[digit]
}

// Discussion
// Prompt from LeetCode: https://leetcode.com/problems/letter-combinations-of-a-phone-number/

// The trickiest part of this prompt is the building up of the unknown number of possible strings. My first attempt used nested loops; one to loop over the input string,
// and one to loop over the possble letter values for each digit in the input string. Each loop added to an array of possible combinations.
// This got messy very quickly because in order to size the array correctly, I would have need separate code to determine the number of possiblities (ie. the
// string "11" has no possible letters, but the string "79" has 16).
// The recursive solution presented here minimizes that difficulty.