1307. Verbal Arithmetic Puzzle

题目信息

题号:

1307

难度:

Hard

主题:

回溯、约束满足、竖式加法

原题:

LeetCode 1307

重点:

不同字母映射到不同数字,同一字母始终映射相同数字;多位单词首字母不能为零

题目重述

给定若干加数单词 words 和结果单词 result。需要为每个出现的字母分配一个 0 到 9 的数字,使不同字母使用不同数字,并把每个单词解释成十进制整数。

任何长度大于一的单词首字母不能映射为零。请判断是否存在一种映射,使所有 words 对应整数之和恰好等于 result 对应整数。

字母总种类不超过 10,所有单词只包含大写英文字母。

自建示例

简单的一位加法存在映射:

输入:words = ["A","B"], result = "C"
输出:true
解释:例如 A=1、B=2、C=3,即可满足 1+2=3。

位数关系不可能满足时无解:

输入:words = ["A","B"], result = "AA"
输出:false
解释:方程为 A+B=11A,即 B=10A;在不同十进制数字约束下不存在解。