17. Letter Combinations of a Phone Number

iterative O(3ⁿ) time

m = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

import itertools as it

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        chars = [m[int(d)] for d in digits]
        return [''.join(p) for p in it.product(*chars)]

m = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        return reduce(lambda res, d : [s + c for s in res for c in m[d]], map(int, digits), [''])

用这个

m = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        res = ['']
        for d in map(int, digits):
            res = [s + c for s in res for c in m[d]]
        return res

m = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        res = ['']
        for d in digits:
            t = []
            for s in res:
                for c in m[int(d)]:
                    t.append(s + c)
            res = t
        return res

dfs

m = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return []
        if len(digits) == 1: return list(m[int(digits)])
        res = self.letterCombinations(digits[: -1]) # 前边的结果已经出来了，只需要计算当前的最后一个字符即可
        return [s + c for s in res for c in m[int(digits[-1])]]

iterative

string m[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

class Solution {
public:
    /*
     * @param digits: A digital string
     * @return: all posible letter combinations
     */
    vector<string> letterCombinations(string &digits) {
        // write your code here
        vector<string> res;
        if (digits.empty()) return res;
        res.push_back(""); // 一定要放一个空串！！！
        for (char d : digits) {
            vector<string> t;
            for (const auto &s : res) {
                for (char c : m[d - '0']) {
                    t.push_back(s + c);
                }
            }
            res.swap(t);
        }
        return res;
    }
};

recursive O(3ⁿ) time

string m[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

class Solution {
public:
    /*
     * @param digits: A digital string
     * @return: all posible letter combinations
     */
    vector<string> letterCombinations(string &digits) {
        // write your code here
        vector<string> res;
        if (digits.empty()) return res;
        dfs("", digits, res);
        return res;
    }

    void dfs(const string &s, const string &d, vector<string> &res) {
        if (s.length() == d.length()) {
            res.push_back(s);
            return;
        }
        for (char c : m[d[s.length()] - '0']) {
            dfs(s + c, d, res);
        }
    }
};