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