Leetcode 17. Letter Combinations of a Phone Number

 

링크는 Leetcode 17. Letter Combinations of a Phone Number

 

 

 

 

 

# 문제이해

숫자가 주어지면, 그 숫자에 조합해서 나올 수 있는 비밀번호를 반환하는 문제인 것 같다. 숫자에 해당하는 알파벳이 있고, 숫자를 눌렀을 때 조합을 구하는 문제. 

 

 

 

# 생각해본 방법

DFS로 풀면 되지 않을까 생각했다. 사진에 보면 output 순서가 알파벳 정렬되어있는 느낌이 있었고, 파이썬 permutation 사용하는것보다, 다른 언어로 풀 때 풀 수 있는 방법이었으면 했다. digit.length가 4인 점도 DFS로 풀라는 느낌이 들었다.

 

- dict 로 숫자와 알파벳을 맵핑하는 사전식 배열을 선언한다.

- digits 값을 돌면서 처리한다

- L값이 digit length 가 될 경우 종료한다.

 

# Try 1. 실패

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        answer = []
        def DFS(L, S):
            dict = {'2':'abc','3':'def', '4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
            if L == len(digits) and S:
                answer.append(S)
                return 
            else:
                for ch in dict[digits[L]]:
                    DFS(L+1, S+ch)
        DFS(0,"")
        return answer

해당 값은 digits 가 "" 일 경우 else 를 탈 때  L이 index out of range 가 뜬다. 

빈 값인지 유효성 검증하는 코드가 필요했다.

 

 

 

# Try 2. 성공

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        answer = []
        def DFS(L, S):
            dict = {'2':'abc','3':'def', '4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
            if L == len(digits) and S:
                answer.append(S)
                return 
            else:
                for ch in dict[digits[L]]:
                    DFS(L+1, S+ch)
        
        if digits:
            DFS(0,"")
        return answer

 

 

통과!