Letter Combinations of a Phone Number (in Python)

Problem

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

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

Example:

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

Note :

Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution

Approach 1 : Consider all possible cases

알고리즘

•각각의 숫자에 해당되는 알파벳을 dictionary 로 만들어서 저장.

•길이가 0일 경우 비어있는 배열 반환.

•길이가 1일 경우 배열을 그대로 반환.

•첫번째 번호에 해당하는 알파벳을 ans에 저장.

•1부터 digits의 길이만큼 for문  실행.

1. 리스트 a에 직전까지의 결과 저장.

2. 리스트 b에 현재 숫자에 해당하는 알파벳 리스트 저장.

3. 리스트 a와 리스트 b를 조합해서 만들 수 있는 단어 리스트를 tmp에 저장.

•리스트 ans 반환.

class Solution:
 
    # Consider all possible cases
    def letterCombinations(self, digits) :
 
        dial = {
            "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"], #
        }
 
        if len(digits) == 0 :
            return []
            
        if len(digits) == 1 :
            return dial[digits]
        
        ans = dial[digits[0]]
 
        for i in range(1, len(digits)) :
 
            a = ans
            b = dial[digits[i]]
            tmp = []
 
            for j in a :
                for k in b :
                    tmp.append(j+k)
 
            ans = tmp
        
        return  ans
 

Complexity Analysis

•Time complexity : \(O(n^2)\).

•Space complexity :\(O(1)\).

---

Approach 2 : Recursive

구글 kickstart에서 실제로 나왔던 유형. 코딩 인터뷰에 상당히 빈도 높게 출제 되는 유형이라고 한다. 확실하게 정리해두자!

알고리즘

•배열 mapping 에 각 인덱스에 해당하는 문자열을 저장. (dictionary보다 훨씬 깔끔하다.)

•recursive 함수 호출.

* recursive 함수

1. recursive 함수에는 변수가 5개 사용된다.

1) ans : 결과 값으로 반환할 배열. 완성된 문자열을 저장.

2) mapping : 각 인덱스에 해당하는 문자열을 저장해둔 배열.

3) r_str : 현재 문자열.

4) cur : 현재 인덱스.

2. 현재 인덱스가 digits의 길이와 같아지면 ans 배열에 현재 문자열을 저장하고 종료.

3. 현재 인덱스가 가리키고 있는 알파벳 리스트의 길이만큼 반복.

1) 현재 인덱스를 (현재 인덱스+1)로

2) 현재 문자열을 (현재 문자열 + 현재 문자)

3) 로 변경한 후 recursive 함수 호출.

class Solution:
 
    # ans   : 결과 값으로 리턴할 배열
    # r_str : 단어
    # cur   : 현재 인덱스
 
    def recursive(self, digits, ans, mapping, r_str, cur) :
 
        if len(digits) == cur :
            ans.append(r_str)
            return
        for e in mapping[int(digits[cur])] :
            self.recursive(digits, ans, mapping, r_str + e, cur+1) 
        
    def letterCombinations(self, digits) :
 
        ans = []
 
        if len(digits) == 0 :
            return ans
 
        mapping = [
            "",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs", #
            "tuv",
            "wxyz", #
        ]
 
        self.recursive(digits, ans, mapping, "", 0)
        return ans

Complexity Analysis

•Time complexity : \(O(m^n)\). m은 하나의 숫자에 해당되는 알파벳들의 평균 갯수. n은 숫자의 길이.

•Space complexity : \(O(1)\).

Source

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