17. Letter Combinations of a Phone Number

Medium

Problem:

When numbers from 2 to 9 are given, print all the letter combinations possible as if they are on a telephone keypad.

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Explanation: 2 can be represented as 'abc' and 3 as 'def', 
so by combining each character, a total of 9 different letter combinations are possible.

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Solution:

DFS

Search through the character array corresponding to each digit using DFS.

1. Split the input value into digits and iterate over them, then iterate over all the character strings corresponding to the number, further recursively searching each character.

2. The dfs() function recursively calls itself until the number of digits matches. Once it has searched to the end, it adds the result and returns.

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def dfs(index, path):
            # Backtracking if searched to the end
            if len(path) == len(digits):
                result.append(path)
                return

            # Iterate over the digits of the input value
            for i in range(index, len(digits)):
                # Iterate over all characters corresponding to the number
                for j in phone[digits[i]]:
                    dfs(i + 1, path + j)

        # Exception
        if not digits:
            return []
        phone = {
                "2": "abc",
                "3": "def",
                "4": "ghi",
                "5": "jkl",
                "6": "mno",
                "7": "pqrs",
                "8": "tuv",
                "9": "wxyz"
                }
        result = []
        dfs(0, "")

        return result

Backtracking

Reference: https://www.youtube.com/watch?v=0snEunUacZY

State Space Tree

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        result = []
        phone = {
                "2": "abc",
                "3": "def",
                "4": "ghi",
                "5": "jkl",
                "6": "mno",
                "7": "pqrs",
                "8": "tuv",
                "9": "wxyz"
        }
        
        def backtrack(i, currentStr):
            if len(currentStr) == len(digits):
                res.append(currentStr)
                return
            for p in phone[digits[i]]:
                backtrack(i + 1, currentStr + p)
        
        if digits:
            backtrack(0, "")
    
        return result

Time complexity will be 4 to the power of n which is the length of the input string multiplies the length of each output string which is going to be the same as the length of the input string: $O(n\times{4^n})$