LeetCode 17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

Difficulty: Medium

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

**Input:** "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.

Solution

Language: Java

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        char[][] chars = {
            {},{},
            {'a', 'b', 'c'},
            {'d', 'e', 'f'},
            {'g', 'h', 'i'},
            {'j', 'k', 'l'},
            {'m', 'n', 'o'},
            {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'},
            {'w', 'x', 'y', 'z'}
        };
        dfsHelper(digits, 0, chars, new char[digits.length()], result);
        return result;
    }
    
    private void dfsHelper(String digits, int index, char[][] chars, char[] cur, List<String> result) {
        if (index >= digits.length()) {
            result.add(new String(cur));
            return;
        }
        char[] cs = chars[digits.charAt(index) - '0'];
        for (int i = 0; i < cs.length; i++) {
            cur[index] = cs[i];
            dfsHelper(digits, index + 1, chars, cur, result);
        }
    }
}