Coder's Cat

LeetCode: Letter Combinations of a Phone Number

2020-12-08

Problem

iven 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.

 img

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Cpp Solution

We build a map from digits to chars, and enumerate all combinations with chars. This is an classic backtracking algorithm.

class Solution {
public:
vector<string> letterCombinations(string digits) {
table['2'] = "abc";
table['3'] = "def";
table['4'] = "ghi";
table['5'] = "jkl";
table['6'] = "mno";
table['7'] = "pqrs";
table['8'] = "tuv";
table['9'] = "wxyz";

vector<string> res;
return dfs(res, digits, 0);
}

vector<string> dfs(vector<string> res, string& digits, int index) {
if(index >= digits.size()) return res;
char ch = digits[index];
vector<string> next;
for(auto& c: table[ch]) {
if(res.size() == 0)
next.push_back(string(1, c));
else {
for(int i=0; i<res.size(); i++) {
next.push_back(res[i] + c);
}
}
}
return dfs(next, digits, index+1);
}

unordered_map<char, string> table;
};

Java Solution

class Solution {
private String letterMap[] = {
" ", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};

private ArrayList<String> res;

public List<String> letterCombinations(String digits) {

res = new ArrayList<String>();
if(digits.equals(""))
return res;

findCombination(digits, 0, "");
return res;
}

private void findCombination(String digits, int index, String s){
if(index == digits.length()){
res.add(s);
return;
}

Character c = digits.charAt(index);
String letters = letterMap[c - '0'];
for(int i = 0 ; i < letters.length() ; i ++){
findCombination(digits, index+1, s + letters.charAt(i));
}
return;
}
}

Preparing for an interview? Checkout this!

Join my Email List for more helpful insights, It's Free!😋