口算难题

难度: Hard

给你一个方程，左边用 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

提示：

2 <= words.length <= 5
1 <= words[i].length, results.length <= 7
words[i], result 只含有大写英文字母
表达式中使用的不同字符数最大为 10

Submission

运行时间: 31 ms

内存: 16.2 MB

import math
class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        L=len(result)
        weights=defaultdict(int)
        no_zero_chars=set()
        for word in words:
            if len(word)>L:
                return False
            if len(word)!=1:
                no_zero_chars.add(word[0])
            base=1
            for c in reversed(word):
                weights[c]+=base
                base*=10
        base=1
        for c in reversed(result):
            weights[c]-=base
            base*=10
        if L>1:
            no_zero_chars.add(result[0])
        
        weights=sorted([[k,v] for k,v in weights.items() if v!=0],key=lambda x:-abs(x[1]))
        used=[False]*10
        # chars={k:-1 for k,_ in weights}
        N=len(weights)
        def dfs(idx,total):
            if idx==N:
                return total==0
            mi=ma=total
            mi_start=ma_start=0
            mi_end=ma_end=9
            for i in range(idx+1,N):
                char,weight=weights[i]
                if weight<0:
                    mi+=weight*mi_end
                    mi_end-=1
                    ma+=weight*ma_start
                    ma_start+=1
                else:
                    mi+=weight*mi_start
                    mi_start+=1
                    ma+=weight*ma_end
                    ma_end-=1
            c,w=weights[idx]
            right=-mi/w
            left=-ma/w
            if w<0:
                left,right=right,left
            left=max(0,math.ceil(left))
            right=min(9,math.floor(right))
            for i in range(left,right+1):
                if used[i]:
                    continue
                if i==0 and c in no_zero_chars:
                    continue
                used[i]=True
                if dfs(idx+1,total+i*w):
                    return True
                used[i]=False
            return False
        return dfs(0,0)

Explain

这个题解使用回溯算法和剪枝优化来解决口算难题。首先，统计每个字符在words和result中出现的权重，权重表示该字符在数字中的位置。然后对权重进行排序，按照绝对值从大到小的顺序。接着使用深度优先搜索进行回溯，尝试为每个字符分配一个数字。在回溯过程中，通过计算当前分配方案的最小值和最大值，并与当前权重和进行比较，来进行剪枝优化。如果找到一个可行的分配方案，就返回True，否则返回False。

时间复杂度: O(10^C), C为字符数

空间复杂度: O(C), C为字符数

import math
class Solution:
    def isSolvable(self, words: List[str], result: str) -> bool:
        L=len(result)
        weights=defaultdict(int)  # 存储每个字符的权重
        no_zero_chars=set()  # 存储不能为0的字符
        for word in words:
            if len(word)>L:  # 如果word长度超过result，无解
                return False
            if len(word)!=1:
                no_zero_chars.add(word[0])  # 长度不为1的word，首字符不能为0
            base=1
            for c in reversed(word):  # 从低位到高位计算字符权重
                weights[c]+=base
                base*=10
        base=1
        for c in reversed(result):  # 从低位到高位计算result字符权重
            weights[c]-=base
            base*=10
        if L>1:
            no_zero_chars.add(result[0])  # result首字符不能为0
        
        weights=sorted([[k,v] for k,v in weights.items() if v!=0],key=lambda x:-abs(x[1]))  # 按绝对值从大到小排序
        used=[False]*10  # 标记数字是否已使用
        N=len(weights)
        def dfs(idx,total):
            if idx==N:  # 所有字符都分配完，检查total是否为0
                return total==0
            mi=ma=total
            mi_start=ma_start=0
            mi_end=ma_end=9
            for i in range(idx+1,N):  # 计算剩余字符的最小值和最大值
                char,weight=weights[i]
                if weight<0:
                    mi+=weight*mi_end
                    mi_end-=1
                    ma+=weight*ma_start
                    ma_start+=1
                else:
                    mi+=weight*mi_start
                    mi_start+=1
                    ma+=weight*ma_end
                    ma_end-=1
            c,w=weights[idx]  # 当前要分配的字符和权重
            right=-mi/w
            left=-ma/w
            if w<0:  # 权重为负，交换left和right
                left,right=right,left
            left=max(0,math.ceil(left))
            right=min(9,math.floor(right))
            for i in range(left,right+1):  # 尝试分配数字
                if used[i]:
                    continue
                if i==0 and c in no_zero_chars:  # 不能分配0
                    continue
                used[i]=True
                if dfs(idx+1,total+i*w):  # 递归分配下一个字符
                    return True
                used[i]=False
            return False
        return dfs(0,0)

Explore

在题解中，剪枝操作是基于当前的字符分配对后续分配可能造成的影响。在回溯过程中，我们首先计算剩余字符如果按照最小可能值或最大可能值分配后可能形成的总和区间，即计算最小可能总和（mi）和最大可能总和（ma）。如果当前字符分配后的新总和不在这个区间内，那么就没有必要继续这个分支的探索，因为它不可能导致总和为零的有效解。这种基于当前选择对未来可能性限制的思考是剪枝的关键。

在口算难题中，我们的目标是使得words数组中的字符串所代表的数值之和等于result字符串所代表的数值。在权重计算时，words中的字符应该是正向累加的，因为它们是被加的数。而result中的字符则需要取相反数，因为在等式中result是被减的数（即words的和应该等于result）。这样，我们最终的目标是使所有字符的总权重乘以对应的数字后的和为零。

这个判断实际上没有考虑到所有字符都映射到0的情况。理论上，如果每个字符都映射到0，那么无论words的长度或result的长度如何，都会满足等式。然而，这种情况在实际问题中通常不会被考虑为有效解，特别是当题目或上下文规定不允许所有数字均为0时。因此，如果word的长度超过result，通常意味着无法通过非零的数字映射来达成等式，因此直接返回False是一种合理的简化处理。

按权重的绝对值从大到小排序的目的是优先处理对总和影响最大的字符。这种策略是基于一个观点：权重大的字符对最终的数值有较大影响，因此先为这些字符分配数字可以更快地观察到分配的效果，增加早期剪枝的可能性，从而减少不必要的回溯。例如，一个权重为1000的字符错误分配的影响，远大于一个权重为10的字符。通过这种方式，可以更有效地缩小搜索空间，加快找到解的速度。