Leetcode 17 Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

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

Input: digits = ""
Output: []

Input: digits = "2"
Output: ["a","b","c"]

• Soruda bizden telefonlarda olan kodlama sistemine göre verilen rakamların kaç farklı harf kombinasyonu olduğunu bulmamızı istiyor.
• Görece kolay bir soru bruteforce ile tüm harf kombinasyonlarını bulabiliriz.
• Yapacağımız ilk şey sayıların karşılığı olan harfleri bir listede tutmak.
• Daha sonra backtrack adında yazdığımız yardımcı fonksiyonu rekursif olarak çağırarak kombinasyonları buluruz.

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