This is a typical backtracking problem. Consider the code travels a tree. Each digit is represented as a node of this tree. Each node has the rest digits as its child node. On each node, the code has number N of letter to pick up. So the code does DFS on this tree to find all of the combination.
To simplify the calculation, consider each digits has 3 letters.
Time Complexity : O ( 3 ** len(s) )
Space Complexity: O ( 3 ** len(s) )
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9":"wxyz"}
result = []
def backtrack(i, tmp):
if i == len(digits):
if tmp:
result.append(tmp)
return
for t in letters[digits[i]]:
backtrack(i+1, tmp + t)
backtrack(0, "")
return result
BFS based solution:
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9":"wxyz"}
if not digits: return []
result = []
queue = deque([[l, 1] for l in letters[digits[0]]])
while queue:
for _ in range(len(queue)):
w , index = queue.popleft()
if index == len(digits):
result.append(w)
else:
for l in letters[digits[index]]:
queue.append([w + l, index + 1])
return result
An iterative solution. Start from the last digit to the first digit, add letter of current digit to the front of last letter combinations.
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits: return []
letters = {'2': 'abc', '3': 'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz' }
ds = [d for d in digits]
result = [[l] for l in letters[ds.pop()]]
while ds:
suffix = result[:]
result = []
for l in letters[ds.pop()]:
for s in suffix:
result.append([l] + s)
return [''.join(t) for t in result]
Edited 04/24/2021. Add the iterative solution.
No comments:
Post a Comment