Start learning free

LESSON 361 OF 574 · BACKTRACKING

Letter Combinations of a Phone Number in Swift: 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

    SWIFT · BACKTRACKING

    Letter Combinations Of A Phone Number in Swift, explained

    Problem overview

    The method letterCombinations receives digits, a string of the digits 2 to 9, and returns every string that those digits could spell on a phone keypad. Each digit stands for the letters on its key (2 is abc, 3 is def, and so on up to 9, which is wxyz; 7 has pqrs). A combination takes one letter from each key, in the order of the digits.

    The combinations must come in keypad order: all those starting with the first letter of the first key, then the second letter, and so on, with the same rule applied to the later digits. For "23" the result is ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]: three letters for 2 times three for 3 makes 9 strings. For "7" it is ["p", "q", "r", "s"]. An empty digits returns an empty array, not an array holding an empty string.

    Approach: choose one letter per digit, then go deeper

    The number of letters to pick depends on the length of digits, so a fixed number of nested loops can't do the job. Backtracking handles it with a function that calls itself once per digit.

    The function keeps the position i of the digit it is spelling and the letters chosen so far in current. It tries each letter of that digit's key, in the key's order, and for each one calls itself for position i + 1 with the letter added to the end of current. When i reaches the number of digits, every digit has a letter and current is a finished combination, so it is saved.

    Trying the letters in the key's order gives exactly the keypad order. For "23", the first letter a is tried first, and the whole subtree below it (ad, ae, af) is finished before b is tried.

    In many backtracking problems a choice has to be undone after the recursive call. Here it doesn't: current + String(letter) builds a new string for each call, and current itself never changes, so the loop's next letter starts from the same prefix.

    Step by step

    1. Create result, an empty [String], for the finished combinations.
    2. Return early for an empty digits with digits.isEmpty. Without this check the search would reach "every digit has a letter" at once, with zero digits, and save the empty string, so letterCombinations("") would return [""] instead of [].
    3. Create the keypad constant, an array of strings indexed by digit: two empty strings for the digits 0 and 1, which have no letters, then "abc" up to "wxyz". The empty places keep each key at its own index, so keypad[7] is "pqrs".
    4. Start the search with backtrack(Array(digits), 0, "", keypad, &result): position 0, nothing chosen yet. Array(digits) turns the string into an array of Character values that can be read by position.
    5. Return result. The helper has added to the same array, so it now holds everything.
    6. Declare the helper backtrack with the parameters digits, i, current, keypad and result, the last one marked inout so that the method can change the caller's array.
    7. Check for the end: if i == digits.count.
    8. Save and return. Inside that if, append current to result and return. No digit is left to spell.
    9. Look up the key. digits[i].wholeNumberValue! turns the character into its number, and keypad[...] gives the letters of that key.
    10. Loop over the letters of that key, in order.
    11. Recurse with i + 1 and current + String(letter), passing &result again.

    The solution in Swift

    class Solution {
    func letterCombinations(_ digits: String) -> [String] {
        var result = [String]()
        if digits.isEmpty {
            return result
        }
        let keypad = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        backtrack(Array(digits), 0, "", keypad, &result)
        return result
    }

    func backtrack(_ digits: [Character], _ i: Int, _ current: String, _ keypad: [String], _ result: inout [String]) {
        if i == digits.count {
            result.append(current)
            return
        }
        let letters = keypad[digits[i].wholeNumberValue!]
        for letter in letters {
            backtrack(digits, i + 1, current + String(letter), keypad, &result)
        }
    }
}

    The Swift details worth a closer look:

    • Strings can't be indexed with an Int. Writing digits[0] on a String is a compile error: 'subscript(_:)' is unavailable: cannot subscript String with an Int, use a String.Index instead. Converting once with Array(digits) gives an array of Character values, and digits[i] works on that array.
    • wholeNumberValue. It is a property of Character and returns an optional Int: 7 for "7", and nil for a character such as "x". The ! unwraps it, which is safe here because the input holds only digits.
    • inout and &. Arrays are values and are copied when passed. An inout parameter lets the helper change the caller's array, and the caller marks the argument with &. Every recursive call receives the same result this way.
    • String(letter). Iterating over a String produces Character values, and + joins strings, so each letter is converted before it is added to current.
    • Values, not references. A String is a value type. Appending current to result stores its own copy, and the strings built by other calls are never touched.

    Complexity

    Time: O(n · 4^n) for n digits. A key has at most 4 letters, so there are at most 4^n combinations, and building each one takes n steps. With the digits "9999" the method returns 256 strings, from "wwww" to "zzzz".

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

    Edge cases and common mistakes

    • Empty input. Without the isEmpty check the method returns [""], one empty combination. The lesson expects [].
    • One digit. "7" returns the four letters of its key, and "2" returns three. The keys of 7 and 9 are the ones with four letters.
    • Counting results. The number of combinations is the product of the key sizes: "79" gives 4 × 4 = 16 strings, from "pw" to "sz", and "234" gives 3 × 3 × 3 = 27, from "adg" to "cfi".
    • Index of the keypad. The array is indexed by the digit itself, which is why it has two empty strings at the start. If they were dropped, every key would be off by two.

    Testing

    • "23" gives ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
    • "7" gives ["p", "q", "r", "s"].
    • "2" gives ["a", "b", "c"].
    • "" gives [].
    • "79" gives 16 strings, the first "pw" and the last "sz".
    Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free