首页 > 代码库 > Leetcode-Letter Combinations of a Phone Number

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

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

Solution:

 1 public class Solution { 2     public List<String> letterCombinations(String digits) { 3         List<String> res = new ArrayList<String>(); 4         List<List<Character>> map = getMap(); 5         char[] comb = new char[digits.length()]; 6         int[] num = new int[digits.length()]; 7         for (int i=0;i<digits.length();i++) num[i] = (digits.charAt(i)-‘0‘)-2; 8         int[] curPos = new int[digits.length()]; 9         Arrays.fill(curPos,-1);10         int level = 0;11         while (level!=-1){12             if (level>=digits.length()){13                 for (int i=0;i<digits.length();i++)14                     comb[i] = map.get(num[i]).get(curPos[i]);15                 String temp = new String(comb);16                 res.add(temp);17                 level--;18                 continue;19             }20             int val = curPos[level];21             if (val+1>=map.get(num[level]).size()){22                 curPos[level]=-1;23                 level--;24                 continue;25             } else {26                 curPos[level]++;27                 level++;28             }29         }30 31         return res;        32     }33 34 35     public List<List<Character>> getMap(){36         int[] val = new int[]{3,3,3,3,3,4,3,4};37         List<List<Character>> map = new ArrayList<List<Character>>();38         int base = -1;39         for (int i=0;i<val.length;i++){40             List<Character> list = new ArrayList<Character>();41             for (int j=0;j<val[i];j++){42                 base++;43                 list.add((char)(‘a‘+base));44             }45             map.add(list);46         }47         return map;48     }49           50 }

 

Leetcode-Letter Combinations of a Phone Number