LeetCode Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

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"].

方法

题目不难，主要是谨记有这种映射关系，出了本文写的用HashMap,也可以用String数组，用String数组有时往往效率会更好，如此题用数组更加方便：

String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

主要思想实际上是dfs,代码如下:

public class Solution {
        List<String> list = new ArrayList<String>();
        public List<String> letterCombinations(String digits) {
            if(digits.length() == 0){
                return new ArrayList<String>();
            }
            Map<Integer,List<Character>> map = new HashMap<Integer,List<Character>>();
            int a = 97;
            for(int i = 2; i <= 9; i++){
                List<Character> list = new ArrayList<Character>();
                list.add((char) (a));
                a++;
                list.add((char)a);
                a++;
                list.add((char)a);
                a++;
                if(i == 7 || i == 9){
                    list.add((char)a);
                    a++;
                }
                map.put(i,list);
            }
            int[] array = new int[digits.length()];
            for(int i = 0; i < digits.length(); i++){
                array[i] = digits.charAt(i)-48;
            }
            find(map,0,digits,new ArrayList<String>());
            return list;
        }
        public void find(Map<Integer,List<Character>> map, int pos, String digits, ArrayList<String> arrayList){
            if(arrayList.size() == digits.length()){
                String str = "";
                for(String s : arrayList){
                    str = str+s;
                }
                list.add(str);
                return;
            }
            List<Character> cList = map.get(digits.charAt(pos)-48);
            for(int i = 0; i < cList.size(); i++){
                arrayList.add(cList.get(i)+"");
                find(map,pos+1,digits,arrayList);
                arrayList.remove(arrayList.size()-1);
            }
        }

}