# Letter Combinations of a Phone Number

MEDIUM

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 digit 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']`.
```/**
Input: digits = "23"
**/

class Solution {

private Map<String, String> keyboard = new HashMap<>();

public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if(digits == null || digits.isEmpty()){
return result;
}
populateKeyBoard();
String current = "";
int n = digits.length();
generateLetterCombinations(result, current, digits, n);
return result;
}

private void generateLetterCombinations(List<String> result, String current, String
remaining_digits, int n){
if(current.length() == n){
}else{
String curDigit = remaining_digits.substring(0, 1);
String curMapping = keyboard.get(curDigit);
int len = curMapping.length();
for(int i = 0 ; i < len ; i++){
String cur = String.valueOf(curMapping.charAt(i));
generateLetterCombinations(result, (current + cur),
remaining_digits.substring(1), n);
}
}
}

private void populateKeyBoard(){
keyboard.put("2", "abc");
keyboard.put("3", "def");
keyboard.put("4", "ghi");
keyboard.put("5", "jkl");
keyboard.put("6", "mno");
keyboard.put("7", "pqrs");
keyboard.put("8", "tuv");
keyboard.put("9", "wxyz");
}
}
```

Complexity Analysis

• Time Complexity : `O(3N × 4M)` where `N` is the number of digits in the input that maps to 3 letters (e.g. `2, 3, 4, 5, 6, 8`) and `M` is the number of digits in the input that maps to 4 letters (e.g. `7, 9`), and `N+M` is the total number digits in the input.
• Space Complexity : `O(3N × 4M)` since one has to keep 3N × 4M solutions.

Categories: Backtracking

Tagged as: