MediumNo. 0017

Letter Combinations of a Phone Number — LeetCode 17 Python Solution

Topics
Hash Table, String, Backtracking
Reading time
2 min

The problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

Example

Input
digits = "23"
Output
["ad","ae","af","bd","be","bf","cd","ce","cf"]

Python solution

PythonSolution
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        d = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        ans = [""]
        for i in digits:
            s = d[int(i) - 2]
            ans = [a + b for a in ans for b in s]
        return ans

Complexity

Time
O(4n)
Space · auxiliary
O(4n)

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 17. Letter Combinations of a Phone Number is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0126Word Ladder IIHard
0140Word Break IIHard
0691Stickers to Spell WordHard
0756Pyramid Transition MatrixMedium
1079Letter Tile PossibilitiesMedium
1096Brace Expansion IIHard

Frequently asked questions

How hard is LeetCode 17. Letter Combinations of a Phone Number?

LeetCode 17. Letter Combinations of a Phone Number is rated Medium on LeetCode.

What is the time complexity of LeetCode 17. Letter Combinations of a Phone Number?

The Python solution on this page runs in O(4n).

What is the space complexity of LeetCode 17. Letter Combinations of a Phone Number?

The Python solution on this page uses O(4n) auxiliary space.

What topics does LeetCode 17. Letter Combinations of a Phone Number cover?

LeetCode 17. Letter Combinations of a Phone Number is tagged Hash Table, String and Backtracking on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.