[1스4코2파] # 222 LeetCode 17. Letter Combinations of a Phone Number

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (222차)
[4코1파] 2023.01.13~ (214일차)
[1스4코1파] 2023.04.12~ (125일차)
[1스4코2파] 2023.05.03 ~ (103일차)

Today :

2023.08.14 [222일차]
backtracking
https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

17. Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
문제 설명

2-9의 숫자가 주어지고 해당 숫자에 매칭되는 문자열이 있을 때, 해당 숫자를 조합한 digits이 주어지면 digits에 매칭되는 문자열의 조합을 return 함

문제 풀이 방법

backtracking으로 푸는데 주어진 digits에 해당하는 digit에 매핑되는 answkdufdmf hash map(dictionary)로 만들어 놓고나서, backtracking에는 index와 현재 문자열을 인자로 받아서, recursive 하게 돈다. base는 역시 index가 주어진 digits의 길이를 넘어가면 안되는 것

내 코드

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

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

        ans = []

        def backtracking(idx, cur):
            if idx == len(digits):
                ans.append(cur)
                return

            digit = digits[idx]
            for letter in letterDict[digit]:
                backtracking(idx+1, cur+letter)

        backtracking(0, '')
        return ans

증빙

여담

첨에 dfs 메소드로 해놓고, 인덱스+1에 조합으로 만든 letter를 넣으니까
자꾸 일부만 출력돼서 진짜 짱났음..
그냥 for문으로 해당 매핑된 letter를 돌면서 idx+1을 해주고 현재 까지 만들어진 문자열에 letter를 더해주는 인자를 넣어서 recursive 하게 풀었어야 했음... 하 쉬운건데 이걸 끝까지 와서 한 줄 때문에 못 풀었네..
이해한 것 같으면서 이해 못한 것 같고 그러면 어떻게 해야하지
그럼 어떻하긴 뭘 어떻게 문제 계속 풀어야지

갬성카페에서 코딩하기 굿