Python Easy DFS Solution


  • 1
    G
    class Solution(object):
        def __init__(self):
            self.memo = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
            
        def letterCombinations(self, digits):
            if not digits:
                return []
            res = []
            self.dfs(digits, 0, "", res)
            return res
        
        def dfs(self, digits, idx, path, res):
            if len(path) == len(digits):
                res.append(path)
                return  # backtrack
            for i in range(idx,len(digits)):
                for c in self.memo[digits[i]]:
                    self.dfs(digits, i+1, path+c, res)

  • 0
    S

    can you explain your code please? i am getting confused about your self.dfs() method.. is it a built_in method? and why we need bfs here? thanks in advance


  • 0
    G

    self.dfs is my helper function, as you can see I defined it below letterCombinations function. The idea is not bfs, but dfs, try to draw this in paper/whiteboard, you will be able to see that I returned to my previous call when len(path) == len(digits), and continue from there


  • 1
    A

    Not a correct answer because in method dfs, there is no need to have double loop. We only need to loop one time. Try this:

    def dfs(self,digits,idx,path,res):
            if idx==len(digits):   // reduce one len() reduce time
                res.append(path)
                return
            for c in self.memo[digits[idx]]:
                self.dfs(digits,idx+1,path+c,res)
    

    DFS is definitely a good way to solve this problem.


  • 0
    L

    @Artix I agreed with your thought


Log in to reply
 

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