17. Letter Combinations of a Phone Number

难度: Medium

题目描述

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 = "2"
Output: ["a","b","c"]

 

Constraints:

• 1 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

解题思路

代码实现

解决方案

java

class Solution {

    public List<String> letterCombinations(String digits) {
        if ("".equals(digits)) {
            return new ArrayList<>();
        }
        Map<Character, String[]> map = new HashMap<>();
        map.put('2', new String[] { "a", "b", "c" });
        map.put('3', new String[] { "d", "e", "f" });
        map.put('4', new String[] { "g", "h", "i" });
        map.put('5', new String[] { "j", "k", "l" });
        map.put('6', new String[] { "m", "n", "o" });
        map.put('7', new String[] { "p", "q", "r", "s" });
        map.put('8', new String[] { "t", "u", "v" });
        map.put('9', new String[] { "w", "x", "y", "z" });
        char[] digitsArray = digits.toCharArray();
        List<String> data = new ArrayList<>();
        backtrack(data, map, "", digitsArray, 0);
        return data;

    }

    private void backtrack(List<String> data, Map<Character, String[]> map, String current, char[] digitsArray,
            int index) {
        if (current.length() == digitsArray.length) {
            data.add(current);
            return;
        }
        char curChar = digitsArray[index];
        String[] curStr = map.get(curChar);
        for (String s : curStr) {
            backtrack(data, map, current + s, digitsArray, index + 1);
        }

    }
}