Leecode #1307. 口算难题

给你一个方程，左边用 words 表示，右边用 result 表示。

你需要根据以下规则检查方程是否可解：

每个字符都会被解码成一位数字（0 - 9）。 每对不同的字符必须映射到不同的数字。 每个 words[i] 和 result 都会被解码成一个没有前导零的数字。 左侧数字之和（words）等于右侧数字（result）。 如果方程可解，返回 True，否则返回 False。

示例

示例 1：

输入：words = ["SEND","MORE"], result = "MONEY"
输出：true
解释：映射 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->'2'
所以 "SEND" + "MORE" = "MONEY" ,  9567 + 1085 = 10652
示例 2：

输入：words = ["SIX","SEVEN","SEVEN"], result = "TWENTY"
输出：true
解释：映射 'S'-> 6, 'I'->5, 'X'->0, 'E'->8, 'V'->7, 'N'->2, 'T'->1, 'W'->'3', 'Y'->4
所以 "SIX" + "SEVEN" + "SEVEN" = "TWENTY" ,  650 + 68782 + 68782 = 138214
示例 3：

输入：words = ["THIS","IS","TOO"], result = "FUNNY"
输出：true
示例 4：

输入：words = ["LEET","CODE"], result = "POINT"
输出：false

解题思路

​ 初步读题，发现这就是小学奥数题啊，简单的说就是多项式求和，多个未知数的和为0，且这些未知数的值为0-9不能重复。暴力枚举dfs肯定是会超时的，这时候就需要剪枝了。根据网友的题解，可以算出后面可能出现的最大值和最小值，来判断当前的取值是否合法，从而达到剪枝的效果，代码如下：

class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        # 1. 在memo中存储每个 未知量 -> 系数
        memo = defaultdict(int)
        for word in words:
            for j, l in enumerate(word[::-1]):
                memo[l] += 10**j    
        for j, l in enumerate(result[::-1]):
            memo[l] -= 10**j
        
        # 3. 根据系数的绝对值进行排序，为后面计算极值剪枝做准备
        memo = list(zip(memo.keys(), memo.values()))
        memo.sort(key=lambda x: abs(x[1]), reverse=True)
        
        # 3. 注意每个word都不能存在前置0，记录前置的字母，用于后面的检测
        pre = set([x[0] for x in chain(words, [result])])
        
        # 4. used元组记录已经使用过的数字
        used = set()
        
        # 5. idx表示下一个要搜索的字母， S表示以及积累的和
        def dfs(idx, S):
            if idx == len(memo): # 5.1 搜索到底部了
                return S == 0
            
            # 5.2 计算后面可能出现的最大值和最小值
            _max, _min, small, big = 0, 0, 0, 9
            for i in range(idx+1, len(memo)):
                while small in used: small += 1
                while big in used: big -= 1
                if memo[i][1] >= 0:    
                    _min += memo[i][1] * small
                    _max += memo[i][1] * big
                else:
                    _min += memo[i][1] * big
                    _max += memo[i][1] * small
                    
            for i in range(10):
                # 5.3 判断i是否被使用过，以及避免前置0的出现
                if i not in used and not (i == 0 and memo[idx][0] in pre):
                    temp_s = S + i* memo[idx][1]
                    # 5.4 通过极值判断取值是否合法
                    if  _min <= -temp_s <= _max: # 5.5 这里temp_s前面加的负号
                        used.add(i)
                        ret = dfs(idx+1, temp_s)
                        if ret:
                            return True
                        used.remove(i) # 5.6 分支搜索完要remove元素
            return False
                    
        return dfs(0, 0)