Python solution with detailed explanation


  • 0
    G

    Solution

    Letter Combinations of a Phone Number https://leetcode.com/problems/letter-combinations-of-a-phone-number/

    General Backtracking Pattern

    class Solution(object):
        def letterCombinations(self, digits):
            """
            :type digits: str
            :rtype: List[str]
            """
            if not digits:
                return []
            mapping = {
                        '2':['a','b','c'],
                        '3':['d','e','f'],
                        '4':['g','h','i'],
                        '5':['j','k','l'],
                        '6':['m','n','o'],
                        '7':['p','q','r','s'],
                        '8':['t','u','v'],
                        '9':['w','x','y','z']
                      }
            all_solns = []
            self.letter_combinations([], 0, digits, all_solns, mapping)
            return all_solns
        
        def letter_combinations(self, so_far, k, digits, all_solns, mapping):
            if k == len(digits):
                all_solns.append("".join(so_far))
            else:
                for c in mapping[digits[k]]:
                    so_far.append(c)
                    self.letter_combinations(so_far, k+1, digits, all_solns, mapping)
                    so_far.pop()
            return
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.