# Three methods (Python)

• First solution (DFS with recursion, 79ms 3.19%):
Care needs to be exercised with recursion because it may not differentiate if the initial string is empty or if you have arrived at a leaf. This is my very slow first solution.

``````class Solution(object):
d={"0":" ", "1":"*", "2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
notfirst = None
def letterCombinations(self, digits):
if not len(digits):
if self.notfirst:
return [""]
else:
return []
self.notfirst = True
l=[]
for i in self.d[digits[0]]:
for j in self.letterCombinations(digits[1:]):
l.append(i+j)
return l
``````

With simple optimization it gets a lot quicker (42ms, 72.65%):

``````class Solution(object):
d={"0":" ", "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 not len(digits):
return []
l=[]
for i in self.d[digits[0]]:
for j in self.letterCombinations2(digits[1:]):
l.append(i+j)
return l
def letterCombinations2(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not len(digits):
return [""]
l=[]
for i in self.d[digits[0]]:
for j in self.letterCombinations2(digits[1:]):
l.append(i+j)
return l
``````

Second solution (BFS with loop, 49ms, 40.93%):
Apparently there are better algorithms with BFS, like appending to temp and replacing ans with temp, but this's what I wrote.

``````class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
d={"0":" ", "1":"*", "2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
if not digits:
return []
l=len(digits)
ans = [[]]
count = 0
for index,i in enumerate(digits):
while len(ans[count])==index:
for j in d[i]:
ans.append(ans[count]+[j])
count+=1
return ["".join(i) for i in ans if len(i)==l]
``````

Final solution (maths???, 62ms, 14.71%):
The intuitive version does not list in alphabetical order, but that can be tweaked and is probably not hard.

``````class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits:
return []
d={"0":" ", "1":"*", "2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
dx={"0":1, "1":1, "2":3, "3":3, "4":3, "5":3, "6":3, "7":4, "8":3, "9":4}
d2=[1]
for i in digits:
d2.append(d2[-1]*dx[i])
return ["".join([d[j][(i//d2[k])%dx[j]] for k,j in enumerate(digits)]) for i in xrange(d2[-1])]
``````

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