Start learning free

LESSON 360 OF 573 · BACKTRACKING

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

    SCALA · BACKTRACKING

    Letter Combinations Of A Phone Number in Scala, explained

    Problem overview

    The method letterCombinations receives digits, a string of at most four characters, each from '2' to '9'. Every digit stands for the letters on its phone key: 2 is abc, 3 is def, and so on up to 9 as wxyz, with four letters on keys 7 and 9. The method returns a List[String] with every string that picks one letter for each digit, in the order of the digits.

    The order matters: the results must come in keypad order. Every combination that starts with the first letter of the first key comes before those that start with its second letter, and the same rule applies to the next digit inside each group. Since each key's letters are alphabetical, this is also alphabetical order.

    For "23" the answer is List(ad, ae, af, bd, be, bf, cd, ce, cf): three letters for 2 times three for 3 gives nine strings. For "7" it is List(p, q, r, s). For the empty string "" it is an empty list: there is nothing to spell, so there are no combinations, not even an empty one.

    Approach: choose one letter per digit

    The number of combinations is the product of the key sizes, so the loops you would write by hand depend on how many digits there are: two nested loops for two digits, three for three. A recursive method avoids that. It handles one digit and calls itself for the next one, so the depth of the recursion is the number of digits.

    This is backtracking. A call at position i tries each letter of the key of digits(i), in the key's order, adds the letter to the string chosen so far, and moves to position i + 1. When i reaches digits.length, every digit has its letter, and the string is a finished combination. Trying the letters in key order produces keypad order with no sorting.

    In many backtracking problems the chosen items are removed again after the recursive call. Here nothing needs undoing: a Scala String never changes, so current + letter creates a new string, and the caller's current stays as it was for its next letter.

    Step by step

    1. Create result, an empty ArrayBuffer[String]() that collects the combinations.
    2. Handle empty input. If digits.isEmpty, return result.toList right away. Without this check, the search would reach the end of the digits immediately and record the empty string as a combination.
    3. Build keypad as 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". With this layout the letters of digit d are keypad(d).
    4. Start the search with backtrack(digits, 0, "", keypad, result): position 0, nothing chosen yet.
    5. Return result.toList, since backtrack filled the same buffer.
    6. Write the helper backtrack, taking the digits, the position i, the letters chosen so far in current, the keypad and the result buffer, and returning Unit.
    7. Stop at the end: when i == digits.length, every digit has a letter.
    8. Record and return. Add current to result and return. The string is immutable, so it can be stored as it is, with no copy.
    9. Look up the letters of this digit with digits(i) - '0'.
    10. Loop over the letters with letter <- letters, in the key's order.
    11. Recurse with i + 1 and current + letter.

    The solution in Scala

    class Solution {
    def letterCombinations(digits: String): List[String] = {
        val result = ArrayBuffer[String]()
        if (digits.isEmpty) {
            return result.toList
        }
        val keypad = Array("", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
        backtrack(digits, 0, "", keypad, result)
        result.toList
    }

    def backtrack(digits: String, i: Int, current: String, keypad: Array[String], result: ArrayBuffer[String]): Unit = {
        if (i == digits.length) {
            result += current
            return
        }
        val letters = keypad(digits(i) - '0')
        for (letter <- letters) {
            backtrack(digits, i + 1, current + letter, keypad, result)
        }
    }
}

    Scala details worth a look:

    • digits(i) - '0' subtracts one Char from another, which gives an Int. For '7' the result is 7, the index of "pqrs" in keypad. Converting the character with toInt would not do: '7'.toInt is the character code, 55.
    • A for over a String visits its characters, so letter is a Char. current + letter appends the character and gives a new String.
    • Array versus ArrayBuffer. The keypad never changes size, so a fixed Array fits. The result grows as combinations are found, so it is an ArrayBuffer, converted to a List at the end.
    • Shared buffer. result is passed to every call, and each call adds to the same buffer. That is why the helper returns Unit and the top-level method returns the buffer's contents after the search.
    • return in the helper ends the call early. It could be written without return by putting the loop in an else branch; both do the same.

    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 takes n steps of string appending.

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

    Edge cases and common mistakes

    • Empty input. The answer must have no combinations. Without the isEmpty check, the search records one empty string, so the result is List("") with size 1 instead of an empty list.
    • A single digit. "7" gives the four letters of its key as four one-letter strings.
    • Keys of different sizes. Digits 7 and 9 have four letters. For "79" the answer has 16 strings, from pw to sz. For "2345" it has 81, from adgj to cfil.
    • Wrong keypad indexing. Leaving out the two placeholders at the start shifts every key by two: the index digits(i) - '0' then points to the wrong letters.
    • Looping over the digits instead of recursing. A fixed number of nested loops only works for one length.

    Testing

    • "23" gives List(ad, ae, af, bd, be, bf, cd, ce, cf).
    • "" gives an empty list.
    • "7" gives List(p, q, r, s).
    • "79" gives 16 strings, starting with pw, px, py, pz, qw and ending with sz.
    • "2345" gives 81 strings, starting with adgj, adgk, adgl and ending with cfil.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free