Letter Combinations of a Phone Number 425

Question

Given a digit string excluded 01, 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.

Notice

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

Example

Given "23"

Return ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Solution

求所有组合自然想到递归。

首先用一个hashmap将每个数字及其对应的字母加入。然后递归求digits上每一位数字对应字母的所有组合。

代码如下：

public class Solution {
    /**
     * @param digits A digital string
     * @return all posible letter combinations
     */
    public ArrayList<String> letterCombinations(String digits) {
        // Write your code here
        ArrayList<String> res = new ArrayList<String>();
        if(digits == null || digits.length() == 0){
            return res;
        }

        HashMap<Character, char[]> map = new HashMap<Character, char[]>();
        map.put('0', new char[] {});
        map.put('1', new char[] {});
        map.put('2', new char[] { 'a', 'b', 'c' });
        map.put('3', new char[] { 'd', 'e', 'f' });
        map.put('4', new char[] { 'g', 'h', 'i' });
        map.put('5', new char[] { 'j', 'k', 'l' });
        map.put('6', new char[] { 'm', 'n', 'o' });
        map.put('7', new char[] { 'p', 'q', 'r', 's' });
        map.put('8', new char[] { 't', 'u', 'v'});
        map.put('9', new char[] { 'w', 'x', 'y', 'z' });

        StringBuilder sb = new StringBuilder();
        helper(digits, map, res, sb, 0);
        return res;
    }

    private void helper(String digits, HashMap<Character, char[]> map, ArrayList<String> res, StringBuilder sb, int pos){
        if(sb.length() == digits.length()){
            res.add(sb.toString());
            return;
        }

        //sb.length()表明当前在哪一位上
        for(char c : map.get(digits.charAt(pos))){
            sb.append(c);
            helper(digits, map, res, sb, pos + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}