Letter Combinations of a Phone Number Leetcode Solution
In this tutorial, we will solve the leetcode problem letter combination in python.
Task:
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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
Solution:
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
lst, s = [], ""
dct = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno', '7':'pqrs','8':'tuv','9':'wxyz'}
if digits is "":
return lst
a = len(digits)
if a == 1:
return [x for x in dct[digits]]
else:
self.recur_approach(digits, dct, lst, s, i=0)
return lst
def recur_approach(self, digits, dct, lst, s, i=0):
if i == len(digits):
lst.append(s)
return
for x in dct[digits[i]]:
self.recur_approach(digits, dct, lst, s+x, i+1)
Steps:
step1: First, we will make an empty list and string to store our combination.
step2: Then, we initiate a dictionary representing the mapping of digits in the keypad to alphabets.
step3: now, if the digits string is empty then we return an empty list or lst, which is our base case.
step4: if the len(digits) is 1 then we simply return the value corresponding to the key as a digit in dct.
step5: else we apply the recursive approach, for which we declared a function recur_approach which takes digits string, dct, lst and empty string s and index i as arguments.
step6: inside the recur_approach function, if i is equal to the length of digits then, we append the s to the last and return.
step7: otherwise we loop for each character in dct corresponding to the key as digits and call the function recursively while appending the combination to the lst and in our letterCombiantions function we return last at the end.
