Python DFS


  • 0
    S

    All the combination/permutation problems can be solved using DFS in similar fashion. This is my version for combination.

    29 ms, beats 90.18%

    class Solution(object):
        def __init__(self):
            self.chars = {'1':"*", '2':"abc", '3':"def",'4':"ghi",'5':"jkl",'6':"mno",'7':"pqrs",'8':"tuv",'9':"wxyz"}
            
        def letterCombinations(self, digits):
            """
            :type digits: str
            :rtype: List[str]
            """
            if digits == "":
                return []
            self.res = []
            self.dfs([], digits, 0)
            return self.res
            
        def dfs(self, path, digits, i):
            if len(digits) == i:
                self.res.append("".join(path))
                return
            for c in self.chars[digits[i]]:
                self.dfs(path + [c], digits, i+1)
            return
    

Log in to reply
 

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