17.Letter_Combinations_Phone_Number.md

17. Letter Combinations of a Phone Number

Recursive solution, each time get first digits and array of letters, Get all different state for this array of range, And in for loop remove first digits go to the next time recursive. If the digits is empty end the recursive.

The time complexity is O(3ⁿ4^m), n is 3 letters digits, m is 4 letters digits.

Tip. This sloution send the result address to recuirse, So Combinations dont need return value.

var Letter = map[string][]string{
	"0": {""},
	"1": {""},
	"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"},
}

func letterCombinations(digits string) []string {
	var result []string
	if digits == "" {
		return result
	}
	b := []byte(digits)
	Combinations(b, "", &result)
	return result
}

func Combinations(digits []byte, prev string, result *[]string) {
	if len(digits) <= 0 {
		*result = append(*result, prev)
		return
	}
	chars := Letter[string(digits[0])]
	for _, c := range chars {
		Combinations(digits[1:], prev+c, result)
	}
}