Recursive and iterative solution

  • 0
    def letterCombinations(self, digits):
        if not digits: return []
        dic = {"1":"", "2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6": "mno",
              "7":"pqrs", "8":"tuv", "9":"wxyz"}
        prev = list(dic[digits[0]])
        for i in range(1, len(digits)):
            cur = []
            for c in dic[digits[i]]: cur += [ cc+c for cc in prev ]
            prev = cur
        return prev
    def letterCombinations(self, digits):
        dic = {"1":[], "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"]}
        def h(digits):
            if not digits: return []
            m = len(digits)/2
            if not m: return dic[digits[0]]
            return [ c+cc for c in h(digits[:m]) for cc in h(digits[m:]) ]
        return h(digits)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.