LC 0017 [M] Letter Combinations of a Phone Number - ALawliet/algorithms GitHub Wiki

non-graph DFS

T: O(4^n)
S: O(4^n)

Lets consider the worst case, where all the digits are either 7 or 9. In which case every option has branching factor of 4. Now for first digit we've 4 options, 4^2 for the digit next to it and similarly 4^n for the digits at nth length.

Now summation of all these terms is 4 + 4^2 + 4^3 + ... + 4^n, which a geometric progressions with first term a = 4 and r = 4, now using standard geometric progression formula total turns out to be of the order of 4^n and thus time complexity should be O(4^n). Now space complexity depends on your implementation a O(n) recursive implementation is straightforward while O(4^n) iterative implementation is really easy to do.

The complexity is O(K^N). non-polynomial. where K is the branching factor

---

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phone = {
            '2':'abc', '3':'def',
            '4':'ghi', '5':'jkl', '6':'mno',
            '7':'pqrs', '8':'tuv', '9':'wxyz'
        }

        def branch(i, path):
            if len(path) == len(digits):
                combinations.append(path)
            else:
                level = phone[digits[i]]
                for node in level: # node = digit
                    branch(i + 1, path + node)
                   
        combinations = [] 
        if not digits: return []
        branch(0, '')
        return combinations