Letter Combinations of a Phone Number

Medium

The problem

On an old phone keypad, 2 = abc, 3 = def, 4 = ghi, 5 = jkl, 6 = mno, 7 = pqrs, 8 = tuv, 9 = wxyz. Given a string of digits, return every letter string it could spell, using one letter per digit. Return an empty list for an empty input.

Example 1
Input: digits = "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
3 letters for the first digit times 3 for the second gives 9 strings.
Example 2
Input: digits = ""
Output: []

Limits

0 ≤ digits.length ≤ 4
Each digit is from 2 to 9
The strings can be returned in any order

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Each digit is one level of the decision tree; its letters are the branches.

The idea

Digit→letters map; DFS(i): for each letter of digits[i] append and recurse on i+1; record when i == len(digits).

Target: O(4^n · n) time

Go function shape

func letterCombinations(digits string) []string

Reference solution

Tested with go test. Try it yourself first, then compare.

// LetterCombinations: each digit is one level of the decision tree and its letters are the branches.
func LetterCombinations(digits string) []string {
	if digits == "" {
		return []string{}
	}
	letters := map[byte]string{'2': "abc", '3': "def", '4': "ghi", '5': "jkl", '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz"}
	out := []string{}
	var build func(i int, cur []byte)
	build = func(i int, cur []byte) {
		if i == len(digits) {
			out = append(out, string(cur))
			return
		}
		for _, c := range []byte(letters[digits[i]]) {
			build(i+1, append(cur, c))
		}
	}
	build(0, nil)
	return out
}

Read the lesson: Backtracking