17. Letter Combinations of a Phone Number

Category	ps/bfs & dfs
Tag	bfs & dfs
Tags
난이도	★★
발행 여부
사이트	Leet code
실수 유형
이해	완벽히 이해
최종 편집 일시	@2021년 11월 25일 오후 10:46
푼 날짜	@2021년 11월 25일 오후 9:59

문제 해설 및 주의사항

원문

번역 및 주의사항

풀이

내 풀이 코드 (dfs)

퇴고

문제 해설 및 주의사항

원문

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.

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"]

번역 및 주의사항

2 에서 9까지의 수로 이루어진 string 이 주어진다.

2 : abc

3 : def

4 : ghi

...

를 나타내는데,

string 에 있는 숫자들을 눌러 만들 수 있는 모든 경우의 letter combination 를 return 하라.

1은 아무것도 없다.

Constraints:

• 0 <= digits.length <= 4

• digits[i] is a digit in the range ['2', '9'].

---

풀이

내 풀이 코드 (dfs)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def dfs(index: int, current_string: string) -> None:
            # If, current_string's length is n
            if len(current_string) == len(digits):
                ans.append(current_string)
                return
            
            else:
                for letter in letters_dict[digits[index]]:
                    dfs(index + 1, current_string + letter)
            
        
        letters_dict = {
            "2" : "abc",
            "3" : "def",
            "4" : "ghi",
            "5" : "jkl",
            "6" : "mno",
            "7" : "pqrs",
            "8" : "tuv",
            "9" : "wxyz"
        }
        
        if not digits:
            return []
        ans = []
        dfs(0, "")

        return ans

• dfs / bfs 의 핵심은 인접 리스트인 듯 하다.
  • 이번 문제의 인접 리스트는 어떤 것인가?
    • index 가 있다면, 다음 index 에 해당하는 letters_dict 의 value 들이 인접 리스트이다.
    • 그러므로, letters_dict[digits[index + 1]] 이 인접 리스트가 되는 것이다.
    • 나머지는 일반적인 dfs 와 동일하다.

---

퇴고