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.
public class Solution { /** * **/ public ArrayList<String> letterCombinations(String digits) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. HashMap<String, String> hash = digitToLetter(); return combineTwo(digits, hash); } // O(N!) private ArrayList<String> combineTwo(String digits, HashMap<String, String> hash){ ArrayList<String> result = new ArrayList<String>(); if(digits.length() == 0){ result.add(""); return result; } String cur_letters = hash.get(digits.subSequence(0, 1)); String remainder = digits.substring(1); ArrayList<String> combinations = combineTwo(remainder, hash); for(String combi : combinations){ for(int i=0;i<cur_letters.length();i++) result.add(cur_letters.charAt(i) + combi); } return result; } // O(N), 将数字和按键上的字母对应起来 private HashMap<String, String> digitToLetter(){ HashMap<String,String> hash = new HashMap<String, String>(); String letters = "abcdefghijklmnopqrstuvwxyz"; for(int i=2,j=0;i<=9;i++){ String sub = letters.substring(j,j+3); j += 3; if(i==7 || i==9){ sub += letters.charAt(j++); } hash.put(i+"", sub); } return hash; } }
注意细节. 没什么难度