[LeetCode] 17. Letter Combinations of a Phone Number

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

2-9까지의 숫자를 포함하는 문자열이 주어지면 숫자가 나타낼 수있는 가능한 모든 문자 조합을 반환합니다. 임의의 순서로 답변을 반환하십시오.

✍️ 풀이

---

해당 문제는 숫자에 할당된 문자들을 어떻게 표현할 것인지를 생각해내야 한다. 당연히 딕셔너리를 통해 저장해두면 된다.

그 후 모든 문자 조합을 구해야하므로 dfs를 사용한다.

dfs에선 넘어온 index 부터 누를 수 있는 범위까지 숫자의 문자들을 선택할 수 있다.
문자 하나를 선택하면 다음 문자를 선택하기 위해 dfs로 또 진입하며 다시 문자를 선택하게 된다.

이 때 중복된 문자를 선택하지 않도록 넘어온 인덱스 이후 부터 문자를 선택하도록 한다.
결과 값은 선택한 문자의 길이가 주어진 숫자의 길이가 같을 때 반환 값에 추가한다.

🛠 코드

---

class Solution:
    # 좀 더 깔끔하게 짤 수 있지만 속도는 비슷하다.
    def letterCombinations(self, digits: str) -> List[str]:
        def dfs(index, path):
            if len(path) == len(digits):
                result.append(path)
                return
            
            for i in range(index, len(digits)):
                for j in dic[digits[i]]:
                    dfs(i + 1, path + j) # i는 조합을 위해 문자가 중복되지 않게 선택할 수 있게 해줌.
                    # path + j로 넘겼기에 pop이나 join을 해줄 필요가 없다는 장점이있다.
        if not digits:
            return []
        
        dic = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        
        result = []
        dfs(0, "")
        return result

---

📝 정리

---

🎈 참고

---

Book 링크