# Letter Combination Of Phone Number Program Solution

We at gradjobopenings.com provide free job alerts of freshers job drives. In this website we list on campus job openings for freshers and off campus job openings for freshers and also work from home job openings. This is the best website to apply for off campus drive in India. Visit our website for government job alerts and private job alerts. We also list free interview notes and study materials, one of the best interview study website.comfortable to face the interviews:

Problem Statment

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.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

```Input: digits = "23"
```

Example 2:

```Input: digits = ""
Output: []
```

Example 3:

```Input: digits = "2"
Output: ["a","b","c"]
```

Constraints:

• `0 <= digits.length <= 4`
• `digits[i]` is a digit in the range `['2', '9']`.

### Approach 1: DFS

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

### Letter Combination Of Phone Number Program Solution In 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();
}
}
};
``````

### Letter Combination Of Phone Number Program Solution In 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);
}
}
}
``````

### Letter Combination Of Phone Number Program Solution In 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
``````

### Approach 2: Iterative

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

### Letter Combination Of Phone Number Program Solution In C++ | 2nd Approach

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

### Letter Combination Of Phone Number Program Solution In JAVA | 2nd Approach

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

### Letter Combination Of Phone Number Program Solution In PYTHON | 2nd Approach

``````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
``````
error: Content is protected !!