LeetCode: Letter Combinations of a Phone Number

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.

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 insights, It's Free!😋

Tags: LeetCode

← Swap Caps Lock and Control Binary Search →