Python BFS with stack similar to tree iterative DFS


  • 0
    D
    class Solution(object):
        def letterCombinations(self, digits):
            hash = {
                '2': 'abc',
                '3': 'def',
                '4': 'ghi',
                '5': 'jkl',
                '6': 'mno',
                '7': 'pqrs',
                '8': 'tuv',
                '9': 'wxyz',
            }
            stack = []
            path = []
            res = []
            curr = (0, 0) # (i, j) ith num in digits with jth char for that num
            while stack or (curr[0] < len(digits) and curr[1] < len(hash[digits[curr[0]]])):
                while curr[0] < len(digits) and curr[1] < len(hash[digits[curr[0]]]):
                    stack.append(curr)
                    path.append(hash[digits[curr[0]]][curr[1]])
                    curr = (curr[0] + 1, 0)
                loc = stack.pop()
                if loc[0] == len(digits) - 1:
                    res.append(''.join(path))
                path.pop()
                curr = (loc[0], loc[1] + 1)
            return res
    

Log in to reply
 

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