1
class Solution:
2
    def isSolvable(self, words: List[str], result: str) -> bool:
3

4
        # reverse words
5
        words = [i[::-1] for i in words]
6
        result = result[::-1]
7
        allWords = words + [result]
8

9
        # chars that can not be 0
10
        nonZero = set()
11
        for word in allWords:
12
            if len(word) > 1:
13
                nonZero.add(word[-1])
14

15
        # numbers selected in backtracking
16
        selected = set()
17
        # char to Int map
18
        charToInt = dict()
19
        mxLen = max([len(i) for i in allWords])
20

21
        def res(i=0, c=0, sm=0):
22
            if c == mxLen:
23
                return 1 if sm == 0 else 0
24
            elif i == len(words):
25
                num = sm % 10
26
                carry = sm // 10
27
                if c >= len(result):
28
                    if num == 0:
29
                        return res(0, c + 1, carry)
30
                    else:
31
                        return 0
32
                # result[c] should be mapped to num if a mapping exists
33
                if result[c] in charToInt:
34
                    if charToInt[result[c]] != num:
35
                        return 0
36
                    else:
37
                        return res(0, c + 1, carry)
38
                elif num in selected:
39
                    return 0
40
                # if mapping does not exist, create a mapping
41
                elif (num == 0 and result[c] not in nonZero) or num > 0:
42
                    selected.add(num)
43
                    charToInt[result[c]] = num
44
                    ret = res(0, c + 1, carry)
45
                    del charToInt[result[c]]
46
                    selected.remove(num)
47
                    return ret
48
                else:
49
                    return 0
50
            else:
51
                word = words[i]
52
                if c >= len(word):
53
                    return res(i + 1, c, sm)
54
                elif word[c] in charToInt:
55
                    return res(i + 1, c, sm + charToInt[word[c]])
56
                else:
57
                    ret = 0
58
                    # possibilities for word[c]
59
                    for j in range(10):
60
                        if (j == 0 and word[c] not in nonZero) or j > 0:
61
                            if j not in selected:
62
                                selected.add(j)
63
                                charToInt[word[c]] = j
64
                                ret += res(i + 1, c, sm + j)
65
                                del charToInt[word[c]]
66
                                selected.remove(j)
67
                    return ret
68

69
        return res() > 0