现在的位置: 首页 > 综合 > 正文

Letter Combinations of a Phone Number

2014年09月05日 ⁄ 综合 ⁄ 共 1334字 ⁄ 字号 评论关闭

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;
    }
}

注意细节. 没什么难度

抱歉!评论已关闭.