pcp/17_2.py at master · michaelhuo/pcp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        mapping = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
        def backtracking(digits: str, key: str) -> List[str]:
            answer = []
            if not digits:
                if not key:
                    return answer
            for c in mapping[key]:
                answer.append(digits + c)
            return answer
        answer = ["",]
        predigits = ""
        for key in digits:
            level = []
            for predigits in answer:
                level += backtracking(predigits, key)
            answer = level
        return answer