Algorithm
Problem Name: 17. Letter Combinations of a Phone Number
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" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = "" Output: []
Example 3:
Input: digits = "2" Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector < string> letterCombinations(string digits) {
vector<string> ans;
int len = digits.length();
if (len == 0) return ans;
vector < string> letters(len);
string temp;
for (int i = 0; i < digits.length(); i++) {
switch(digits[i]) {
case '2':
letters[i] = "abc";
break;
case '3':
letters[i] = "def";
break;
case '4':
letters[i] = "ghi";
break;
case '5':
letters[i] = "jkl";
break;
case '6':
letters[i] = "mno";
break;
case '7':
letters[i] = "pqrs";
break;
case '8':
letters[i] = "tuv";
break;
case '9':
letters[i] = "wxyz";
break;
default:
break;
}
}
letterCombinationsHelper(ans, temp, 0, letters);
return ans;
}
void letterCombinationsHelper(vector < string> &ans, string &temp, int depth, vector<string> letters) {
if (depth == letters.size()) {
ans.push_back(temp);
return;
}
for (int j = 0; j < letters[depth].size(); j++) {
temp.push_back(letters[depth][j]);
letterCombinationsHelper(ans, temp, depth + 1, letters);
temp.pop_back();
}
}
};
int main() {
string digits = "23";
Solution s;
vector < string> ans = s.letterCombinations(digits);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << endl;
}
return 0;
}
Input
digits = "23"
Output
["ad","ae","af","bd","be","bf","cd","ce","cf"]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string>res;
if(digits.empty()) return res;
vector < string>letter({"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"});
string path = "";
DFS(digits, 0, path, res, letter);
return res;
}
void DFS(string digits, int pos, string& path, vector < string>& res, vector<string>& letter){
if(pos == digits.size()){
res.push_back(path);
return;
}
for(auto c: letter[digits[pos] - '0']){
path.push_back(c);
DFS(digits, pos + 1, path, res, letter);
path.pop_back();
}
}
};
Input
digits = ""
Output
[]
#3 Code Example with Java Programming
Code -
Java Programming
start coding...
class Solution {
private final List LETTER_MAPPING = Arrays.asList("abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz");
public List < String> letterCombinations(String digits) {
List result = new ArrayList<>();
helper(digits, 0, new StringBuilder(), result);
return result;
}
private void helper(String digits, int idx, StringBuilder sb, List < String> result) {
if (idx == digits.length()) {
if (sb.length() > 0) {
result.add(new String(sb.toString()));
}
return;
}
int mappingIdx = Character.getNumericValue(digits.charAt(idx)) - 2;
for (char c : LETTER_MAPPING.get(mappingIdx).toCharArray()) {
sb.append(c);
helper(digits, idx + 1, sb, result);
sb.deleteCharAt(sb.length() - 1);
}
}
}
Input
digits = "2"
Output
["a","b","c"]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const letterCombinations = function(digits) {
if (digits === "") {
return [];
}
const charMap = {
2: ["a", "b", "c"],
3: ["d", "e", "f"],
4: ["g", "h", "i"],
5: ["j", "k", "l"],
6: ["m", "n", "o"],
7: ["p", "q", "r", "s"],
8: ["t", "u", "v"],
9: ["w", "x", "y", "z"]
};
const res = [];
const matrix = [];
for (let i = 0; i < digits.length; i++) {
matrix.push(charMap[digits.charAt(i)]);
}
let tmp = matrix[0];
for (let j = 1; j < matrix.length; j++) {
tmp = helper(matrix, j, tmp);
}
return tmp;
};
function helper(matrix, rowIdx, arr) {
const res = [];
for (let i = 0; i < arr.length; i++) {
const preStr = arr[i];
for (let j = 0; j < matrix[rowIdx].length; j++) {
res.push(`${preStr}${matrix[rowIdx][j]}`);
}
}
return res;
}
Input
digits = "23"
Output
["ad","ae","af","bd","be","bf","cd","ce","cf"]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def letterCombinations(self, digits):
dic, res = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}, [""]
for dig in digits:
tmp = []
for y in res:
for x in dic[dig]: tmp.append(y + x)
res = tmp
return res if any(res) else []
Input
digits = ""
Output
[]
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _017_LetterCombinationsOfAPhoneNumber
{
public IList < string> LetterCombinations(string digits)
{
string[] phoneChars = new string[] { " ",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
if (digits.Length == 0) return new List();
var results = new List < string>() { "" };
foreach (var digit in digits)
{
var keys = phoneChars[digit - '0'];
if (keys.Length == 0) continue;
var temp = new List < string>();
foreach (var result in results)
foreach (var ch in keys)
temp.Add(result + ch.ToString());
results = temp;
}
if (results.Count == 1 && results[0] == "") results.Clear();
return results;
}
}
}
Input
digits = "2"
Output
["a","b","c"]