Letter Combinations of a Phone Number [LeetCode 48]

Frequency: ♥ ♥ ♥                Difficulty: ♥ ♥ ♥
Data Structure: String
Algorithm: iteratively, recursively, level order traversal, backtrace, DFS

Problem Description

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.

问题分析

条条道路通罗马，这道题迭代、递归、层次遍历（在这里类似动态规划）、回溯（DFS）等方法都可以求解。注意到数字’0’和’1’是不代表任何字符的，所以碰到后直接跳过。

解法一

层次遍历，从左往右依次读取数字，将解析的字母加入到之前解析的结果中。由于题目要求输出所有的结果，所以时间复杂度和空间复杂度都和输出成正比，为O(3^N)~O(4^N)之间。由于解析新的数字是加在前一个数字的解析结果之上，所有也可以理解为动态规划。

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<String>();
        if(digits==null) return result;
        char[] digitsAry = digits.toCharArray();
        ArrayList<StringBuilder> parent = new ArrayList<StringBuilder>();
        parent.add(new StringBuilder());
        HashMap<Character, char[]> dict = new Dictionary().dict;
        for(char digit : digitsAry) {
            if(digit=='0'||digit=='1') continue;
            ArrayList<StringBuilder> current = parent;
            parent = new ArrayList<StringBuilder>();
            char[] list = dict.get(digit);
            for(StringBuilder sb : current) {
                for(char c : list) {
                    StringBuilder newSb = new StringBuilder(sb);
                    newSb.append(c);
                    parent.add(newSb);
                }
            }
        }
        for(StringBuilder sb : parent)
            result.add(sb.toString());
        return result;
    }
    // inner class
    class Dictionary {
        HashMap<Character, char[]> dict;
        Dictionary() {
            dict = new HashMap<Character, char[]>();
            char[] char2 = {'a', 'b', 'c'};
            char[] char3 = {'d', 'e', 'f'};
            char[] char4 = {'g', 'h', 'i'};
            char[] char5 = {'j', 'k', 'l'};
            char[] char6 = {'m', 'n', 'o'};
            char[] char7 = {'p', 'q', 'r', 's'};
            char[] char8 = {'t', 'u', 'v'};
            char[] char9 = {'w', 'x', 'y', 'z'};
            dict.put('2', char2 );
            dict.put('3', char3 );
            dict.put('4', char4 );
            dict.put('5', char5 );
            dict.put('6', char6 );
            dict.put('7', char7 );
            dict.put('8', char8 );
            dict.put('9', char9 );
        } 
    }    
}

解法二

采用回溯的方法进行构建。

public class Solution {
    private List<String> result = new ArrayList<String>();
    private StringBuilder sb = new StringBuilder();
    Map<Character, char[]> map = new HashMap<Character, char[]>();
    // main entry
    public List<String> letterCombinations(String digits) {
        if (digits==null) return result;
        // construct the dict
        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' });
        // helper
        letterCombinations(digits, 0);
        return result;
    }
    // helper
    private void letterCombinations(String digits, int idx) {
        if (idx==digits.length()) {
            result.add(sb.toString());
            return;
        }
        for (char c : map.get(digits.charAt(idx))) {
            sb.append(c);
            letterCombinations(digits, idx+1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }    
}

 

查看更多LeetCode解题思路…