Question

link

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Stats

Frequency 3
Diffficulty 3
Adjusted Difficulty 3
Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

There are 2 considerations associated with this question:

  1. How to convert an number into a String (i.e. 2->’abc’ etc.)

  2. How the search works.

Convert number to string

There are 2 way: math way, or the hashmap way.

My initial idea is to calculate it mathematically:

private String getLetters(int key) {
    if (key <= 1 || key >= 10) return "";
    // key must be in the range of [2,9]
    char first = (char) ('a' + (key - 2) * 3);
    if (key >= 8) first++;
    String letters = "";
    for (int i = 0; i < 4; i++) {
        if (i == 3 && !(key == 7 || key == 9)) {
            break;
        }
        letters += first++;
    }
    return letters;
}
String letters = getLetters('3' - '0');

However, most people would use HashMap. It’s not the main issue anyway, so using HashMap is fine.

Solution

This is very typical “Permutation” question. Need to memorize clearly.

Refer to ninechap for the solution and a piece of very standard code.

My code

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<String>();
        if (digits == null || digits.length() == 0) {
            ans.add("");
            return ans;
        }
        int len = digits.length();
        // this type of DFS question is very standardized
        helper(ans, "", digits, 0, len);
        return ans;
    }

    private void helper(List<String> ans, String path, String digits, int pos, int len) {
        if (pos == len) {
            ans.add(path);
            return;
        }
        // check the char at position 'pos', and find all possible letters to insert
        String possibleLetters = getLetters(digits.charAt(pos));
        for (char letter: possibleLetters.toCharArray()) {
            helper(ans, path + letter, digits, pos + 1, len);
        }
    }

    private String getLetters(char digit) {
        // first convert char to integer
        int index = digit - '0';
        String[] map = new String[] {
            " ",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };
        // second, find corresponding string from map
        return map[index];
    }
}