# Python easy to understand backtracking solution.

• ``````def letterCombinations(self, digits):
if not digits:
return []
dic = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
res = []
self.dfs(digits, dic, 0, "", res)
return res

def dfs(self, digits, dic, index, path, res):
if len(path) == len(digits):
res.append(path)
return
for i in xrange(index, len(digits)):
for j in dic[digits[i]]:
self.dfs(digits, dic, i+1, path+j, res)``````

• I have similar idea but different implementation with make each dfs do more work.

``````from collections import defaultdict

class Solution(object):
def letterCombinations(self, digits):
if not digits: return []
q = [self.table[c] for c in digits]
return self.dfs(q)

def dfs(self, queue, re=''):
if not queue:
return [re]
return [x for c in queue[0] for x in self.dfs(queue[1:], re+c)]

def __init__(self):
self.table, start = defaultdict(list), 96
for i in range(2, 10):
count = 4 if i in [7, 9] else 3
for _ in range(count):
start += 1
self.table[str(i)].append(chr(start))
``````

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