Input: digits = '69'
Output: ['mw', 'mx', 'my', 'mz', 'nw', 'nx', 'ny', 'nz', 'ow', 'ox', 'oy', 'oz']

In Plain English

New to this one? Start here. Below is the core idea in everyday language, plus a real-world analogy—then the sections that follow build on it with the formal reasoning, code, and step-by-step walkthroughs.

Intuition

At each digit in the string, we have a decision to make: which letter will this digit represent? Based on this decision, let's illustrate the state space tree that represents the choices at each digit of the input string.

State space tree
Consider the input string "69". Let's start with the root node of the tree, which is an empty string:

At the first digit, 6, we have the choice of starting our combination with 'm', 'n', or 'o':

For each of these combinations we've created, we now have a new decision to make: which letter of digit 9 ('w', 'x', 'y', 'z') should we choose? These choices are illustrated below:

One important thing missing from this state space tree is information on which digit we're making a decision on at each node. We can use an index i to determine which digit we're considering at each node:

The final level of this decision tree (i.e., when i == n, where n denotes the length of the input string) represents all possible combinations that can be created from the provided string. Similar to our approach in Find All Subsets, let's use backtracking to obtain these keypad combinations.

Mapping digits to letters
The final thing we need to figure out is a way to determine which letters correspond to which digits. A hash map is great for this purpose. In the hash map, digits are the keys, and the associated sets of letters are their values. This allows us to access the letters in constant time:

Implementation

def phone_keypad_combinations(digits: str) -> List[str]:
    keypad_map = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }
    res = []
    backtrack(0, [], digits, keypad_map, res)
    return res

def backtrack(i: int, curr_combination: List[str], digits: str,
             keypad_map: Dict[str, str], res: List[str]) -> None:
    # Termination condition: if all digits have been considered, add the
    # current combination to the output list.
    if len(curr_combination) == len(digits):
        res.append("".join(curr_combination))
        return
    for letter in keypad_map[digits[i]]:
       # Add the current letter.
        curr_combination.append(letter)
        # Recursively explore all paths that branch from this combination.
        backtrack(i + 1, curr_combination, digits, keypad_map, res)
        # Backtrack by removing the letter we just added.
        curr_combination.pop()

#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

void backtrack(int i, string& current, string& digits,
               unordered_map<char, string>& keypad, vector<string>& res) {
    if ((int)current.size() == (int)digits.size()) {   // chose a letter per digit
        res.push_back(current);                        // record a COPY
        return;
    }
    string letters = keypad[digits[i]];
    for (int c = 0; c < (int)letters.size(); c++) {
        current.push_back(letters[c]);                 // choose
        backtrack(i + 1, current, digits, keypad, res);
        current.pop_back();                            // undo
    }
}

vector<string> phoneKeypadCombinations(string digits) {
    if (digits.empty()) {
        return {};
    }
    unordered_map<char, string> keypad = {
        {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
        {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
    };
    vector<string> res;
    string current;
    backtrack(0, current, digits, keypad, res);
    return res;
}

// These methods live inside a class, e.g. class Solution { ... }
List<String> phoneKeypadCombinations(String digits) {
    if (digits.isEmpty()) {
        return new ArrayList<>();
    }
    Map<Character, String> keypad = new HashMap<>();
    keypad.put('2', "abc"); keypad.put('3', "def"); keypad.put('4', "ghi");
    keypad.put('5', "jkl"); keypad.put('6', "mno"); keypad.put('7', "pqrs");
    keypad.put('8', "tuv"); keypad.put('9', "wxyz");
    List<String> res = new ArrayList<>();
    backtrack(0, new StringBuilder(), digits, keypad, res);
    return res;
}

void backtrack(int i, StringBuilder current, String digits,
               Map<Character, String> keypad, List<String> res) {
    if (current.length() == digits.length()) {   // chose a letter per digit
        res.add(current.toString());             // record a COPY
        return;
    }
    String letters = keypad.get(digits.charAt(i));
    for (int c = 0; c < letters.length(); c++) {
        current.append(letters.charAt(c));       // choose
        backtrack(i + 1, current, digits, keypad, res);
        current.deleteCharAt(current.length() - 1);   // undo
    }
}

Complexity Analysis

Time complexity: The time complexity of phone_keypad_combinations is $O(n\cdot 4^n)$. This is because the state space tree will branch down until a decision is made for all $n$ elements. This results in a tree of height $n$ with a branching factor of 4 since there are up to 4 decisions we can make at each digit. For each of the $4^n$ combinations created, we convert it into a string and add it to the output list, which takes $O(n)$ time per combination. This results in a total time complexity of $O(n\cdot 4^n)$.

Space complexity: The space complexity is $O(n)$ due to the recursive call stack, which can grow up to a maximum depth of $n$. The keypad_map only takes constant space since there are only 8 key-value pairs.

Dry Runs

Two step-by-step walkthroughs of the algorithm below: a valid case (the expected happy path) and an invalid / edge case that exercises the tricky parts. Each step shows the program state as the code runs—the same steps apply to Python, C++ and Java.

The same steps in each language

Interview Tip

Tip: Check if you can skip trivial implementations.

During an interview, it's crucial to manage your time effectively. If you encounter a trivial and time-consuming task, such as creating the keypad_map in this problem, it's possible the interviewer may allow you to skip it or implement it later if there's time left in the interview. Ensure you at least briefly mention how the implementation you're skipping would work before requesting to move on to the core logic of the problem.