Start learning free

LESSON 360 OF 573 · BACKTRACKING

Letter Combinations of a Phone Number in Go: Backtracking

Practice O(n · 4n) Read the full explanation

Given a string digits made of the digits 2 to 9, return every letter combination the number could spell on a phone keypad.

Each digit stands for the letters on its key:

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

A combination takes one letter from each digit's key, in the order of the digits. Return the combinations in keypad order: every combination that starts with the first letter of the first digit's key comes before every combination that starts with its second letter, and so on; inside each of those groups, the same rule for the second digit, then the third. (Each key's letters are in alphabetical order, so this is also alphabetical order.)

If digits is empty, there is nothing to spell: return no combinations at all, not one empty string.

 

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Explanation: 2 gives a, b or c, and 3 gives d, e or f: 3 × 3 = 9 combinations.
The three that start with a come first, in the order of 3's letters; then the ones that start with b, then c.

Example 2:

Input: digits = ""
Output: []
Explanation: No digits, so there are no combinations.

Example 3:

Input: digits = "7"
Output: ["p","q","r","s"]
Explanation: With one digit, each letter of its key is a combination. The keys 7 and 9 have four letters, the others three.

 

Constraints:

  • 0 <= digits.length <= 4
  • Each character of digits is a digit from '2' to '9'.

Note:

The tutorial uses backtracking. Walk through digits one position at a time, keeping the letters chosen so far in a string current. At position i, try each letter of the key of digits[i], in the key's order: add it to the end of current and go on to position i + 1. When the position reaches the end of digits, every digit has its letter: save current. Trying the letters in the key's order gives exactly the keypad order above. Each call gets its own longer string, so nothing has to be undone when a call returns.

Each key has at most 4 letters, so n digits give at most 4n combinations, and building one takes n steps: the time is O(n · 4n). Besides the answer, the search keeps at most O(n) calls open at a time, one per digit (their strings add up to O(n2) characters at most).

STEP 1 OF 11
    Ctrl + Enter to check

    GO · BACKTRACKING

    Letter Combinations Of A Phone Number in Go, explained

    Problem overview

    The function letterCombinations receives a string digits made of the characters '2' to '9' and returns every string those keys could spell on a phone keypad. Digit 2 stands for abc, 3 for def, and so on up to 9 for wxyz. A combination takes one letter from each digit's key, in the order of the digits, and the answer lists them in keypad order: all combinations that start with the first letter of the first key come first, then those that start with its second letter, and so on, with the same rule applied to each later digit.

    For "23" the answer is [ad ae af bd be bf cd ce cf]: three letters for 2 times three letters for 3 gives nine combinations. For "7" it is [p q r s], since keys 7 and 9 have four letters. For an empty digits there is nothing to spell, and the function returns no combinations at all, which is not the same as one empty string.

    Approach: choose one letter per digit

    The number of nested loops would depend on the length of digits, which you can't write directly. Backtracking solves this with recursion. Walk through digits one position at a time and keep the letters chosen so far in a string, current. At position i, try each letter of the key for digits[i], in the key's order: add it to current and recurse on position i + 1. When i reaches the end of digits, every digit has its letter, and current is a finished combination.

    Trying the letters in the key's order is what produces keypad order, so no sorting is needed. A Go string never changes, and current + string(letter) builds a new string for each call. That means nothing has to be removed from current when a call returns, which is the undo step you often see in backtracking code.

    Tracing "23"

    The first call has i = 0 and current = "". For digit 2 it tries a, b and c. The call with current = "a" reaches digit 3 and tries d, e and f, saving ad, ae, af. Then the branch for b saves bd, be, bf, and the branch for c saves cd, ce, cf. Running this gives [ad ae af bd be bf cd ce cf].

    Step by step

    1. Create result as an empty []string. It collects the combinations.
    2. Return early for empty input. If len(digits) == 0, return result. Without this check the search would save the empty string as one combination.
    3. Build keypad, a []string indexed by digit. Places 0 and 1 hold empty strings, which keeps every other key at its own index: keypad[7] is "pqrs".
    4. Start the search with backtrack(digits, 0, "", keypad, &result): position 0, no letters chosen, and the address of result.
    5. Return result, which now holds every combination.
    6. Write the helper backtrack next to the main function. It takes the digits, the position i, current, the keypad and a pointer to the result slice, and returns nothing.
    7. Handle the end. When i == len(digits), every digit has a letter.
    8. Save the combination. Append current to *result, store the slice back, and return.
    9. Find this digit's letters. digits[i]-'0' converts the character into its number, which is the index into keypad.
    10. Loop over the letters with range, in order.
    11. Recurse with i+1 and current+string(letter).

    The solution in Go

    func letterCombinations(digits string) []string {
	result := []string{}
	if len(digits) == 0 {
		return result
	}
	keypad := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	backtrack(digits, 0, "", keypad, &result)
	return result
}

func backtrack(digits string, i int, current string, keypad []string, result *[]string) {
	if i == len(digits) {
		*result = append(*result, current)
		return
	}
	letters := keypad[digits[i]-'0']
	for _, letter := range letters {
		backtrack(digits, i+1, current+string(letter), keypad, result)
	}
}

    The Go details worth a closer look:

    • Why a pointer to the slice. append may return a slice with a new backing array. If backtrack received a plain []string, its append would only change its own copy of the slice header, and letterCombinations would not see the new elements. With result *[]string the helper writes the new slice through *result.
    • Bytes and runes. digits[i] is a byte, such as 55 for '7'. The digit characters are consecutive, so subtracting '0' gives 7. Ranging over a string yields runes, so letter is a rune (97 for 'a'), and string(letter) turns it back into a one-letter string.
    • Indexing with the byte. The subtraction matters. Using digits[i] directly as an index would look at position 50 for '2', and a ten-element slice panics with index out of range [50] with length 10.
    • Immutable strings. current + string(letter) creates a new string and leaves current untouched, so each letter of the loop starts from the same prefix.

    Complexity

    Time: O(n · 4^n) for n digits. A key has at most four letters, so there are at most 4^n combinations, and building each one costs about n steps for the string concatenations.

    Space: O(n) beyond the answer itself. The recursion is n calls deep, and each holds a string of at most n letters.

    Edge cases and common mistakes

    • Empty input. letterCombinations("") returns [], with length 0. Without the early return, the call to backtrack would reach i == len(digits) immediately and return [""], a list with one empty string.
    • Four-letter keys. "79" gives 4 × 4 = 16 combinations, starting with pw px py pz and ending with sx sy sz. Four digits of 7 and 9, such as "7979", give 256.
    • Mixed lengths. "2345" gives 3 × 3 × 3 × 3 = 81 combinations. "92" gives [wa wb wc xa xb xc ya yb yc za zb zc]: the first digit changes slowest.
    • A missing -'0'. The index would be the character code, not the digit, and the program would panic.
    • Not saving the slice back. Calling append(*result, current) without assigning the result discards the combination.

    Testing

    • "23" gives [ad ae af bd be bf cd ce cf].
    • "" gives [].
    • "7" gives [p q r s].
    • "92" gives [wa wb wc xa xb xc ya yb yc za zb zc].
    • "79" gives 16 combinations, and "2345" gives 81.
    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free