[Backtracking] 17. Letter Combinations of a Phone Number ★

17. Letter Combinations of a Phone Number

 

GPT: 백트레킹

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 1. 숫자와 문자 매핑 정의
        phone_map = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
        }
        
        # 2. 결과 리스트 초기화
        res = []
        
        # 3. 입력이 빈 문자열인 경우 빈 리스트 반환
        if not digits:
            return res
        
        # 4. 백트래킹 함수 정의
        def backtrack(index, path):
            # 4.1 조합이 완성되면 결과에 추가
            if index == len(digits):
                res.append("".join(path))
                return
            
            # 4.2 현재 숫자에 해당하는 문자 탐색
            possible_letters = phone_map[digits[index]]
            for letter in possible_letters:
                # 선택 및 다음 단계 진행
                path.append(letter)  # 현재 문자 추가
                backtrack(index + 1, path)  # 다음 숫자로 이동
                path.pop()  # 현재 문자 제거 (백트래킹)

        # 5. 백트래킹 시작
        backtrack(0, [])
        return res

 

GPT: BFS

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 1. 숫자와 문자 매핑 정의
        phone_map = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
        }
        
        # 2. 입력이 빈 문자열인 경우 빈 리스트 반환
        if not digits:
            return []
        
        # 3. BFS를 위한 큐 초기화
        queue = deque([""])  # 초기값은 빈 문자열
        
        # 4. 각 숫자에 대해 처리
        for digit in digits:
            possible_letters = phone_map[digit]  # 현재 숫자의 문자들
            for _ in range(len(queue)):
                combination = queue.popleft()  # 현재 조합을 가져옴
                for letter in possible_letters:
                    queue.append(combination + letter)  # 새 조합을 큐에 추가
        
        # 5. 최종 결과 반환
        return list(queue)

 

https://youtu.be/0snEunUacZY?si=5iLG5JXFBOD7yD6C

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        digitToChar = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz',
        }        

        res = []  # 결과를 저장할 리스트

        # 백트래킹 함수 정의
        def backtrack(i, curStr):
            # 현재 조합의 길이가 입력된 숫자의 길이와 같으면 결과에 추가
            if len(curStr) == len(digits):
                res.append(curStr)
                return
            # 현재 숫자에 해당하는 문자들로 조합 생성
            for c in digitToChar[digits[i]]:
                backtrack(i + 1, curStr + c)  # 다음 숫자로 이동
        
        # 입력이 빈 문자열인 경우 빈 리스트 반환
        if digits:
            backtrack(0, "")  # 백트래킹 시작
        return res  # 결과 반환

 

3차: 2024.12.26

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        res = []

        digit_to_letters = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz',
        }

        # 백트래킹 함수 정의
        def backtrack(curStr):
            # 종료 조건: 현재 문자열 길이가 입력된 숫자 길이와 같으면
            if len(curStr) == len(digits):
                res.append(curStr)  # 결과 리스트에 현재 문자열 추가
                return  # 재귀 종료
            
            # 현재 숫자에 해당하는 문자들에 대해 반복
            for c in digit_to_letters[digits[len(curStr)]]:
                # 다음 문자 추가하여 백트래킹 재귀 호출
                backtrack(curStr + c)

        # 입력된 digits가 비어있지 않으면 백트래킹 시작
        if digits:
            backtrack("")  # 초기 상태에서 빈 문자열로 시작
        
        return res  # 최종 결과 반환

 

이제.. 품

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 결과를 저장할 리스트
        res = []

        # 숫자와 해당 숫자에 매핑된 문자들
        digit_to_letters = {
            '2': 'abc',  # 숫자 2는 'abc'로 매핑
            '3': 'def',  # 숫자 3은 'def'로 매핑
            '4': 'ghi',  # 숫자 4는 'ghi'로 매핑
            '5': 'jkl',  # 숫자 5는 'jkl'로 매핑
            '6': 'mno',  # 숫자 6은 'mno'로 매핑
            '7': 'pqrs', # 숫자 7은 'pqrs'로 매핑
            '8': 'tuv',  # 숫자 8은 'tuv'로 매핑
            '9': 'wxyz', # 숫자 9는 'wxyz'로 매핑
        }

        # 백트래킹 함수 정의
        def backtrack(subset, idx):
            # 기저 조건: 모든 숫자를 처리한 경우
            if idx >= len(digits):
                # 현재 생성된 문자 조합을 결과에 추가
                res.append("".join(subset.copy()))
                return

            # 현재 숫자(digits[idx])에 매핑된 문자들을 순회
            for sub in digit_to_letters[digits[idx]]:
                # 현재 문자를 부분 조합(subset)에 추가
                subset.append(sub)
                # 다음 숫자를 처리하기 위해 재귀 호출
                backtrack(subset, idx + 1)
                # 상태 복구 (백트래킹)
                subset.pop()

        # 입력이 비어 있지 않은 경우에만 백트래킹 시작
        if digits:  # digits가 빈 문자열이면 백트래킹을 호출하지 않음
            backtrack([], 0)

        # 결과 리스트 반환
        return res

 

최종 코드

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 숫자-문자 매핑 (전화기 자판 기준)
        digit_to_letters = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz',
        }

        res = []  # 결과 리스트

        # 빈 입력인 경우 바로 빈 리스트 반환
        if len(digits) == 0:
            return []

        # 백트래킹 함수 정의
        def backtrack(i, digits, curStr):
            # 현재까지 만든 조합(curStr)의 길이가 digits와 같아지면 결과에 추가
            if len(curStr) == len(digits):
                res.append(curStr)
                return

            # 현재 위치 i의 숫자(digits[i])에 대응되는 문자들 순회
            for c in digit_to_letters[digits[i]]:    
            	"""
                # ⚠️ 주의: curStr += c는 in-place 변경으로,
                # 재귀 호출 이후 되돌릴 수 없음 (문제 생길 수 있음)
                # → 따라서 backtrack(i+1, digits, curStr + c)처럼
                #     재귀 호출 시 새로운 문자열로 전달하는 것이 안전함
                # curStr += c는 in-place 문자열 변경 임
                """                
                # 주의 !!!
                # backtrack 함수 넣을때만 curStr 에 c 가 추가되어야되서 
                # backtrack(i+1, digits, curStr + c) 로 Call 하는게..
                # 같은 i+1 로, digit_to_letters[digits[i]] 의 원소인 각 다른 c 로 ..
                
                backtrack(i + 1, digits, curStr + c)

        # 백트래킹 시작
        backtrack(0, digits, "")
        return res

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        res = []

        # 숫자 → 문자 매핑
        phone = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz"
        }

        def dfs(i, curStr):
            if i==len(digits):
                res.append(curStr)
                return # 종료 !! <-- 잊으면 안됨.

            for s in phone[digits[i]]:
                dfs(i+1, curStr+s)
        
        dfs(0, "")
        return res