Problem
Given a string of digits 2-9, return all possible letter combinations the number could represent (like old phone keypad).
Example
Input: "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]Solution
Backtracking. For each digit, try each of its letters and recurse.
def letter_combinations(digits):
if not digits: return []
mapping = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
result = []
def backtrack(i, path):
if i == len(digits):
result.append(''.join(path))
return
for ch in mapping[digits[i]]:
path.append(ch)
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return resultfunction letterCombinations(digits) {
if (!digits) return [];
const map = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'};
const result = [];
function backtrack(i, path) {
if (i === digits.length) { result.push(path); return; }
for (const ch of map[digits[i]]) backtrack(i + 1, path + ch);
}
backtrack(0, '');
return result;
}void backtrack(string& digits, vector<string>& m, int i, string path, vector<string>& result) {
if (i == digits.size()) { result.push_back(path); return; }
for (char ch : m[digits[i] - '0']) backtrack(digits, m, i + 1, path + ch, result);
}
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};
vector<string> m = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vector<string> result;
backtrack(digits, m, 0, "", result);
return result;
}public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits.isEmpty()) return result;
String[] map = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
backtrack(digits, map, 0, new StringBuilder(), result);
return result;
}
private void backtrack(String digits, String[] map, int i, StringBuilder path, List<String> result) {
if (i == digits.length()) { result.add(path.toString()); return; }
for (char ch : map[digits.charAt(i) - '0'].toCharArray()) {
path.append(ch);
backtrack(digits, map, i + 1, path, result);
path.deleteCharAt(path.length() - 1);
}
}Complexity
- Time: O(4ⁿ)
- Space: O(n)
Explanation
Each digit maps to 3-4 letters. The recursion tree has depth equal to the input length, branching factor 3-4.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?