17.md

17. 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.

R2

class Solution { public List letterCombinations(String digits) { if (digits.isEmpty()) return new LinkedList(); String[] strs = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    LinkedList<String> res = new LinkedList<String>();
    res.add("");
    for (int i = 0; i < digits.length(); i++) {
        while (res.peek().length() == i) {
            String t = res.remove();
            for (char c : strs[Character.getNumericValue(digits.charAt(i))].toCharArray())
                res.add(t + c);
        }
    }
    return res;
}

}

class Solution { private final String[] LETTERS = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations(String digits) {
    if (digits.isEmpty()) return new LinkedList<String>();
    return permute(digits, new StringBuilder(), new ArrayList<>(), 0);
}

private List<String> permute(String digits, StringBuilder cur, List<String> res, int i) {
    if (i == digits.length()) {
        res.add(cur.toString());
    } else {
        char[] arr = LETTERS[digits.charAt(i) - '0'].toCharArray();
        for (char c : arr) {
            cur.append(c);
            permute(digits, cur, res, i + 1);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
    return res;
}

}

R1

my thoughts:

1. sort the array, iterater from left, for each i, set l-pointer to i+1 and r-pointer to [-1], find all pairs till pointers cross; update res when new set is found.
O(n^2) 

my solution:

**********35ms
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        d = {
            '2': list('abc'),
            '3': list('def'),
            '4': list('ghi'),
            '5': list('jkl'),
            '6': list('mno'),
            '7': list('pqrs'),
            '8': list('tuv'),
            '9': list('wxyz'),
            '0': [' ']
        }
        
        def helper(dig, d):
            if len(dig) == 0:
                return []
            if len(dig) == 1:
                return d[dig]
            res = []
            prev = helper(dig[:-1], d)
            
            for c in d[dig[-1]]:
                for st in prev:
                    #print st, c
                    res.append(st+c)
            return res
        return helper(digits, d)

my comments:

from other ppl's solution:

1. N/A