17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

Input: 
"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) Java

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> rst = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return rst;
        }
        Map<Character, List<Character>> map = new HashMap<>();
        map.put('2', Arrays.asList('a','b','c'));
        map.put('3', Arrays.asList('d','e','f'));
        map.put('4', Arrays.asList('g','h','i'));
        map.put('5', Arrays.asList('j','k','l'));
        map.put('6', Arrays.asList('m','n','o'));
        map.put('7', Arrays.asList('p','q','r','s'));
        map.put('8', Arrays.asList('t','u','v'));
        map.put('9', Arrays.asList('w','x','y','z'));
        Set<String> set = new HashSet<>();
        helper(digits, map, set, "");
        Iterator<String> iter = set.iterator();
        while (iter.hasNext()) {
            rst.add((String)iter.next());
        }
        return rst;
    }

    private void helper(String digits, Map<Character, List<Character>> map, Set<String> set, String word) {
        if (digits.length() == 0) {
            set.add(word);
            return;
        }
        char c = digits.charAt(0);
        for (char s : map.get(c)) {
            helper(digits.substring(1), map, set, word+Character.toString(s));
        }
    }
}

Another way using iterative algorithm:

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> rst = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return rst;
        }
        Map<Character, List<Character>> map = new HashMap<>();
        map.put('2', Arrays.asList('a','b','c'));
        map.put('3', Arrays.asList('d','e','f'));
        map.put('4', Arrays.asList('g','h','i'));
        map.put('5', Arrays.asList('j','k','l'));
        map.put('6', Arrays.asList('m','n','o'));
        map.put('7', Arrays.asList('p','q','r','s'));
        map.put('8', Arrays.asList('t','u','v'));
        map.put('9', Arrays.asList('w','x','y','z'));
        char[] chars = digits.toCharArray();
        Queue<String> q = new LinkedList<>();
        for (char c : chars) {
            List<Character> list = map.get(c);
            if (q.size() == 0) {                
                list.stream().forEach(a->q.offer(String.valueOf(a)));
            } else {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    String str = q.poll();
                    list.stream().forEach(a->q.offer(str+a));
                }
            }
        }
        rst.addAll(q);
        return rst;
    }


}

(2) Python

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        strQ = collections.deque()
        mapping = {'2':['a','b','c'],'3':['d','e','f'],'4':['g','h','i'],'5':['j','k','l'],'6':['m','n','o'],'7':['p','q','r','s'],'8':['t','u','v'],'9':['w','x','y','z']}
        for i in xrange(len(digits)):
            chars = mapping[digits[i]]
            if len(strQ) == 0:
                strQ.extendleft(chars)
            else:
                for j in xrange(len(strQ)):
                    c = strQ.pop()
                    for cc in chars:
                        strQ.appendleft(c+cc)
        return strQ

通常这种题目如果colletion中前面的结果要用在后面的结果，就可以考虑用python reduce或scala foldLeft

(3) Scala

object Solution {
    def letterCombinations(digits: String): List[String] = {
        if (digits.isEmpty()) {
            return Nil
        }
        val mapping = Map('2'->List('a','b','c'), '3'->List('d','e','f'), '4'->List('g','h','i'), '5'->List('j','k','l'), '6'->List('m','n','o'), '7'->List('p','q','r', 's'), '8'->List('t','u','v'), '9'->List('w','x','y','z'))
        return digits.foldLeft(List("")){(rst, d)=>rst.flatMap{r=>mapping(d).map{r+_}}}
    }
}