Python Easy DFS Solution

  • 1
    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):
                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

    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

    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

    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
            for c in self.memo[digits[idx]]:

    DFS is definitely a good way to solve this problem.

  • 0

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