[리트코드] 17. Letter Combinations of a Phone Number

# 문제 설명

2~9까지의 수가 주어질 때, 나타날 수 있는 모든 가능한 문자 조합들을 반환해라.

단, 1은 주어지지 않는다.

 

# 입출력 예시

입력	출력
"23"	["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
""	[]
"2"	["a", "b", "c"]

 

# 코드 풀이 1.  key가 int인 경우

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        ltr = {2:'abc', 3:'def', 4:'ghi', 5:'jkl', 6:'mno', 7:'pqrs', 8:'tuv', 9:'wxyz'}
        answer = []
        
        def select(i, path):
            if len(path) >= len(digits):
                answer.append("".join(path))
                return
            
            for x in ltr[int(digits[i])]:
                path.append(x)
                select(i+1, path)
                path.pop()
                
        if digits:
            select(0, [])
        return answer

key가 int이면 Runtime 속도가 24ms로, str일 때보다 더 빠르다.

 

# 코드 풀이 2.  key가 str인 경우

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        ltr = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
        answer = []
        
        def select(i, path):
            if len(path) >= len(digits):
                answer.append(path)
                return
            
            for x in ltr[digits[i]]: # 숫자에 해당하는 문자
                select(i+1, path+x)
                
        if digits:
            select(0, '')
        return answer

key가 str이면 더 가독성이 좋고, 직관적이다. 또 메모리가 13.8MB로 int일 때보다 더 적게 든다.

 

 

# 핵심 포인트

- list로 문자를 추가하려면 append()를 사용해야 하는데, str을 사용하면 +로 더 간단히 추가할 수 있다.

- dict의 key가 int형이면 더 빠르게 검색할 수 있다.