Python Easy DFS Solution

• ``````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)``````

• 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

• `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

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

• @Artix I agreed with your thought

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