Letter Combinations of a Phone Number
- 1 min read
- LC-Medium
- Backtracking
3 years ago
Solution
| Time | Space | Explanation |
|---|---|---|
O(3^N × 4^M) | O(O(3^N × 4^M)) | n = number of digits that map to 3 letters (2, 3, 4, 5, 6, 8), m = number of digits that map to 4 letters (7, 9) |
function letterCombinations(digits: string): string[] {
const n = digits.length;
if (n === 0) {
return [];
}
const mapping = {
2: 'abc',
3: 'def',
4: 'ghi',
5: 'jkl',
6: 'mno',
7: 'pqrs',
8: 'tuv',
9: 'wxyz'
};
const combinations = [];
function dfs(i: number, cur: string[]) {
if (i === n) {
combinations.push(cur.join(''));
return;
}
for(const digit of mapping[digits[i]]) {
cur.push(digit);
dfs(i + 1, cur);
cur.pop();
}
}
dfs(0, []);
return combinations;
};