[LeetCode][Python3] 17. Letter Combinations of a Phone Number

풀이 1

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits=="": return []
        result=[]
        letter={'2':['a','b','c'],'3':['d','e','f'],'4':['g','h','i'],'5':['j','k','l'],'6':['m','n','o'],'7':['p','q','r','s'],'8':['t','u','v'],'9':['w','x','y','z']}
        def dfs(prefix: str,digits:str,length:int):
            if(length == len(digits)):
                result.append(prefix)
                return
            else:
                for i in letter[digits[length]]:
                    dfs(prefix+i,digits,length+1) 
                    
        dfs("",digits,0)
        return result

너무 느리다.

Runtime: 40 ms, faster than 6.50% of Python3 online submissions for Letter Combinations of a Phone Number.
Memory Usage: 14.2 MB, less than 42.48% of Python3 online submissions for Letter Combinations of a Phone Number.

 

풀이 2

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits=="": return []
        result=[]
        letter={'2':['a','b','c'],'3':['d','e','f'],'4':['g','h','i'],'5':['j','k','l'],'6':['m','n','o'],'7':['p','q','r','s'],'8':['t','u','v'],'9':['w','x','y','z']}
        def dfs(prefix:str,digits:str):
            if(len(digits)==0):
                result.append(prefix)
                return
            for i in letter[digits[0]]:
                dfs(prefix+i,digits[1:])
        dfs("",digits)
        return result

함수의 매개변수 length를 없애고, digits의 크기를 줄이는 방법을 사용하자 속도가 비교적 상승하였다.
매개변수 값을 저장하는 stack의 연산이 줄어서 그런 것 같다.

Runtime: 32 ms, faster than 55.41% of Python3 online submissions for Letter Combinations of a Phone Number.
Memory Usage: 14.4 MB, less than 21.04% of Python3 online submissions for Letter Combinations of a Phone Number.