[leetcode/backtracking] 17. Letter Combinations of a Phone Number

문제 링크

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

 

 

문제 설명

 

간단한 백트래킹 문제

 

문제 해결과정

이번 문제는 어렵지는 않았고 테스트케이스도 전부 통과를 했지만 문제를 풀기위한 접근을 조금은 어색하게 한 부분이 있었기에 그 부분을 짚고 넘어가고자 한다.

 

letters = [[],[],['a','b','c'],['d','e','f'],['g','h','i'],['j','k','l'],['m','n','o'],['p','q','r','s'],['t','u','v'],['w','x','y','z']]

class Solution:

    def backtracking(arr,ans, digits,results):
        if len(ans) == len(digits):
            print(ans)
            if ans not in results:
                results.append(ans)
            return

        for i in range(len(arr)):
            if arr[i] in letters[int(digits[len(ans)])]:
                Solution.backtracking(arr, ans+arr[i], digits,results)



    def letterCombinations(self, digits: str) -> List[str]:
        arr = []
        for i in range(len(digits)):
            index = int(digits[i])
            for j in range(len(letters[index])):
                arr.append(letters[index][j])

        results = []
        Solution.backtracking(arr,'',digits, results)
        print(arr)

        if len(results) == 1 and results[0] == "":
            return []

        # return list(set(results))
        return results

 

나는 arr이라는 배열에 사용할 수 있는 모든 letter를 넣었는데 이렇게 하니 나중에 중복된 부분을 따로 처리해줘야 하는 불편함이 있었다. letters라는 배열을 backtracking이라는 함수에서 사용하고 그걸로 for문을 돌면되는데 굳이 arr을 만들어 준것이다.. (이번 문제를 풀면서 정말 알고리즘의 중요성을 깨달았다. 단순 코테를 통과하기 위해서가 아니라 코테를 공부하며 코드를 잘짜기 위한 훈련을 할 수 있기 때문이다.)

 

문제를 풀고 참고한 답

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

        def backtrack(idx, comb):
            if idx == len(digits):
                res.append(comb[:])
                return
            
            for letter in digit_to_letters[digits[idx]]:
                backtrack(idx + 1, comb + letter)

        res = []
        backtrack(0, "")

        return res

 

위 풀이를 보면 정석대로 깔끔하게 코딩을 한 것을 알 수 있다. 자료구조를 객체로 하니 굳이 인덱스를 숫자로 바꿔줄 필요도 없다. 이 코드를 보고 많이 배웠다.