• Time:O(n4^n)
• Space:O(4^n)

## C++

``````class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty())
return {};

vector<string> ans;

dfs(digits, 0, "", ans);
return ans;
}

private:
const vector<string> digitToLetters{"",    "",    "abc",  "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};

void dfs(const string& digits, int i, string&& path, vector<string>& 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();
}
}
};
``````

## JAVA

``````class Solution {
public List<String> letterCombinations(String digits) {
if (digits.isEmpty())
return new ArrayList<>();

List<String> 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<String> ans) {
if (i == digits.length()) {
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);
}
}
}
``````

## Python

``````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
``````

• Time:O(n4^n)
• Space:O(4^n)

## C++

``````class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty())
return {};

vector<string> ans{""};
const vector<string> digitToLetters{"",    "",    "abc",  "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};

for (const char d : digits) {
vector<string> temp;
for (const string& s : ans)
for (const char c : digitToLetters[d - '0'])
temp.push_back(s + c);
ans = move(temp);
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public List<String> letterCombinations(String digits) {
if (digits.isEmpty())
return new ArrayList<>();

List<String> ans = new ArrayList<>();
final String[] digitToLetters = {"",    "",    "abc",  "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};

for (final char d : digits.toCharArray()) {
List<String> temp = new ArrayList<>();
for (final String s : ans)
for (final char c : digitToLetters[d - '0'].toCharArray())
ans = temp;
}

return ans;
}
}
``````

## Python

``````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
``````