Start learning free

LESSON 355 OF 568 · BACKTRACKING

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

    C++ · BACKTRACKING

    Letter Combinations Of A Phone Number in C++, explained

    Problem overview

    The method letterCombinations receives a string digits made of the characters '2' to '9' and returns a vector<string> with every string those digits could spell on a phone keypad. Each digit stands for the letters on its key: 2 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.

    The answer must be in keypad order: all combinations that start with the first letter of the first key come first, then those with its second letter, and inside each group the same rule applies to the next digit. For "23" the result has 3 × 3 = 9 strings: ["ad","ae","af","bd","be","bf","cd","ce","cf"]. With "7" it is ["p","q","r","s"], because key 7 has four letters. An empty digits gives an empty vector, not a vector holding one empty string.

    Approach: choose one letter per position

    The number of nested loops would have to match the number of digits, and that number isn't known in advance. Recursion solves this: one call handles one position and loops over the letters of that digit's key. For each letter it calls itself for the next position.

    The call keeps the letters chosen so far in a string current. When the position reaches the end of digits, every digit has a letter and current is a complete combination, so the call saves it. Trying the letters in the key's order is enough to produce the keypad order, because the first digit's choice changes the slowest and the last digit's choice the fastest.

    This is backtracking: build a partial answer, extend it in every possible way, and return to the earlier choice to try the next. Here nothing has to be undone after a call, because each call receives its own longer string (current + letter) and the caller's current is untouched.

    For "79" the result has 16 strings, starting with "pw", "px", "py", "pz" and ending with "sz".

    Step by step

    1. Create the result. An empty vector<string> named result collects the combinations.
    2. Return early for empty input. With no digits the search below would reach its end at once and save the empty string as if it were a combination. Returning the empty result is the answer the problem asks for.
    3. Build the keypad table. A vector<string> indexed by digit holds each key's letters. The entries for 0 and 1 are empty strings; they never appear in the input, but they keep every other key at its own index.
    4. Start the search with position 0, an empty current, the keypad and the result.
    5. Return the result. The helper added to the same vector, so it now holds everything.
    6. Declare the helper. backtrack returns void and takes digits, the position i, the string current, the keypad and the result. The reference solution takes the vectors and digits by reference and current by value.
    7. Test for the end. When i equals digits.size(), no digit is left to spell.
    8. Save and return. Push current into result; push_back stores a copy, so later calls can't change it.
    9. Look up the letters. digits[i] - '0' turns the character into the number, which indexes the keypad.
    10. Loop over those letters with a range-based for, which visits a string's characters in order.
    11. Recurse. Call backtrack for position i + 1 with current + letter.

    The solution in C++

    class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if (digits.empty()) {
            return result;
        }
        vector<string> keypad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backtrack(digits, 0, "", keypad, result);
        return result;
    }

    void backtrack(string& digits, int i, string current, vector<string>& keypad, vector<string>& result) {
        if (i == digits.size()) {
            result.push_back(current);
            return;
        }
        string letters = keypad[digits[i] - '0'];
        for (char letter : letters) {
            backtrack(digits, i + 1, current + letter, keypad, result);
        }
    }
};

    The C++ details worth a closer look:

    • References versus copies. vector<string>& result makes the helper append to the caller's vector. A plain vector<string> parameter would be a copy, and everything added to it would be lost when the call ended. current has no & on purpose: each call needs its own string.
    • digits[i] - '0'. Indexing a string gives a char. The digit characters are consecutive, so subtracting '0' gives the digit's value: '7' - '0' is 7. Using digits[i] directly as the index would read far past the end of the 10-element vector, which is undefined behaviour.
    • current + letter. Adding a char to a string builds a new string with that letter at the end. It is a temporary, passed by value, so the loop's next iteration starts again from the unchanged current.
    • Signed and unsigned. digits.size() is unsigned, and i is an int. The comparison works for small non-negative values like these, and compilers may warn about mixing the two.
    • The empty-string argument. The literal "" converts to a string for the by-value current. The first parameter is a non-const reference, which is why the call passes the variable digits and not a literal.

    Complexity

    Time: O(n · 4^n) for n digits. Each key has at most 4 letters, so there are at most 4^n combinations, and building and copying each takes about n steps.

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

    Edge cases and common mistakes

    • Empty input. Without the digits.empty() check, the empty input returns a vector holding one empty string (size 1, a single "") instead of an empty vector.
    • One digit. "7" gives ["p","q","r","s"] and "2" gives ["a","b","c"]: a key can have three or four letters.
    • Repeated digits. "9999" gives 256 strings, 4^4, from "wwww" to "zzzz". That is the largest input the constraints allow.
    • Forgetting - '0'. The character '2' has the code 50, not 2, so the lookup leaves the keypad vector.
    • Passing result by value. The code compiles and runs, but the caller's vector stays empty.
    • Wrong keypad entries. The keypad needs the two empty entries at the front. Without them, keypad[2] would hold the letters of 4.

    Testing

    • "23" gives 9 strings: ["ad","ae","af","bd","be","bf","cd","ce","cf"].
    • "" gives [].
    • "7" gives ["p","q","r","s"].
    • "234" gives 27 strings, from "adg" to "cfi".
    • "79" gives 16 strings, from "pw" to "sz".
    • "9999" gives 256 strings.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free