# 17. Letter Combinations of a Phone Number

## Approach 1: DFS

• Time: $O(n4^n)$
• Space: $O(4^n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: vector letterCombinations(string digits) { if (digits.empty()) return {}; vector ans; dfs(digits, 0, "", ans); return ans; } private: const vector digitToLetters{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; void dfs(const string& digits, int i, string&& path, vector& ans) { if (i == digits.length()) { ans.push_back(path); return; } for (const char letter : digitToLetters[digits[i] - '0']) { path.push_back(letter); dfs(digits, i + 1, move(path), ans); path.pop_back(); } } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public List letterCombinations(String digits) { if (digits.isEmpty()) return new ArrayList<>(); List ans = new ArrayList<>(); dfs(digits, 0, new StringBuilder(), ans); return ans; } private static final String[] digitToLetters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; private void dfs(String digits, int i, StringBuilder sb, List ans) { if (i == digits.length()) { ans.add(sb.toString()); return; } for (final char c : digitToLetters[digits.charAt(i) - '0'].toCharArray()) { sb.append(c); dfs(digits, i + 1, sb, ans); sb.deleteCharAt(sb.length() - 1); } } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] digitToLetters = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'] ans = [] def dfs(i: int, path: List[chr]) -> None: if i == len(digits): ans.append(''.join(path)) return for letter in digitToLetters[ord(digits[i]) - ord('0')]: path.append(letter) dfs(i + 1, path) path.pop() dfs(0, []) return ans 

## Approach 2: Iterative

• Time: $O(n4^n)$
• Space: $O(4^n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: vector letterCombinations(string digits) { if (digits.empty()) return {}; vector ans{""}; const vector digitToLetters{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; for (const char d : digits) { vector temp; for (const string& s : ans) for (const char c : digitToLetters[d - '0']) temp.push_back(s + c); ans = move(temp); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public List letterCombinations(String digits) { if (digits.isEmpty()) return new ArrayList<>(); List ans = new ArrayList<>(); ans.add(""); final String[] digitToLetters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; for (final char d : digits.toCharArray()) { List temp = new ArrayList<>(); for (final String s : ans) for (final char c : digitToLetters[d - '0'].toCharArray()) temp.add(s + c); ans = temp; } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] ans = [''] digitToLetters = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'] for d in digits: temp = [] for s in ans: for c in digitToLetters[ord(d) - ord('0')]: temp.append(s + c) ans = temp return ans