LeetCode 1307. 口算难题

字数 3534 2025-12-05 08:27:56

LeetCode 1307. 口算难题

题目描述

给你一个方程，用字符串数组 words 表示一个单词的列表，用字符串 result 表示结果。如果这个方程可解，返回 True，否则返回 False。

每个单词 words[i] 和 result 都被转换成十进制数，规则是：每个字母映射到一个数字（0-9），不同的字母不能映射到相同的数字，并且每个 words[i] 和 result 不能有前导零（即，每个单词的第一个字符不能映射到0）。如果映射后，sum(words[i]) = result 成立，则方程可解。

例如：
输入：words = ["SEND","MORE"], result = "MONEY"
输出：true
解释：我们可以将字母映射为：
S->9, E->5, N->6, D->7, M->1, O->0, R->8, Y->2
那么 "SEND" = 9567, "MORE" = 1085, 和为 10652。
"result" = "MONEY" = 10652，所以返回 true。

这是一个典型的字母算术谜题，也称为密码算术。解题核心是回溯 + 剪枝。

解题过程

这个问题本质上是为不同的字母分配不同的数字（0-9），使得算式成立。由于字母种类通常最多10个，直接尝试所有排列（10! ≈ 3.6百万）是可行的，但需要高效的剪枝。我们可以用列竖式的方法，从低位到高位逐列计算，并在过程中利用进位进行剪枝。

第一步：问题建模与数据准备

收集所有出现的字母：从 words 和 result 中提取所有不同的字母。如果字母种类超过10，直接返回 false，因为10个数字无法分配给超过10个字母。
建立权重系统：我们需要知道每个字母在最终算式“数值”中的权重（即，它是“个位”、“十位”还是“百位”？）。
算式是：sum(words) = result。
我们可以转化为：sum(words) - result = 0。
更巧妙的方法是，为每个字母分配一个系数（权重）：
- 对于 words 中的每个单词，字母出现在第 k 位（从右往左，个位为0），它的系数就加 10^k。
- 对于 result 中的每个字母，出现在第 k 位，它的系数就减 10^k。
  最终，我们希望找到一个数字到字母的映射，满足：对所有字母的 (系数 * 分配的数字)求和 等于 0。
标记首字母不能为零：记录哪些字母是任何单词或结果的首字母，它们不能映射到0。

第二步：回溯算法设计

我们用一个 map（或数组）记录字母到数字的映射，用一个 used 数组记录数字是否已被使用。从权重最高的字母开始尝试分配数字，可以更快地触发剪枝。

然而，更经典的回溯方式是为每个位置（列）进行搜索，模拟竖式加法。这里我们讲解基于系数的回溯方法，因为它更直观且易于实现剪枝。

预处理：
- 计算出每个字母的系数（一个整数值，可正可负）。
- 收集所有需要分配数字的唯一字母列表。
- 将字母列表按照系数的绝对值从大到小排序。这样优先处理权重大的字母，可以让总和更快地偏离0，从而尽早剪枝。
- 记录首字母限制。
深度优先搜索（DFS）：
- 状态：当前搜索到第几个字母（index），当前所有已分配字母的加权和（total），以及当前的数字使用情况。
- 递归基：如果 index 等于字母列表的长度，说明所有字母都已分配。检查 total 是否为0，是则返回 true，否则返回 false。
- 选择列表：数字0-9，但需满足：数字未被使用；如果是首字母，则不能为0。
- 剪枝策略：这是算法的关键！
  - 在尝试为当前字母 char 分配数字 digit 时，我们计算新的总和 newTotal = total + coeff[char] * digit。
  - 我们可以提前计算剩下未分配的字母，它们能提供的最大正贡献和最小负贡献（基于系数和剩余可用数字）。如果即使我们给所有正系数字母分配尽可能大的剩余数字，给所有负系数字母分配尽可能小的剩余数字，newTotal 仍然大于0，那么后续无论如何分配都无法使总和归零。同理，如果即使我们给所有正系数字母分配尽可能小的剩余数字，给所有负系数字母分配尽可能大的剩余数字，newTotal 仍然小于0，也无法归零。这两种情况都可以直接剪枝。

第三步：举例说明（SEND + MORE = MONEY）

字母与系数（从右向左，个位权重为1）：
- 个位列：D + E = Y + carry0 (进位初始0)。但我们用统一系数法：
  - 对于 SEND：S(1000), E(100), N(10), D(1)
  - 对于 MORE：M(1000), O(100), R(10), E(1)
  - 对于 MONEY：M(-10000), O(-1000), N(-100), E(-10), Y(-1)
- 合并系数：
  - M: 1000 (MORE) + (-10000) (MONEY) = -9000
  - O: 100 (MORE) + (-1000) (MONEY) = -900
  - S: 1000 (SEND) = 1000
  - E: 100 (SEND) + 1 (MORE) + (-10) (MONEY) = 91
  - N: 10 (SEND) + (-100) (MONEY) = -90
  - D: 1 (SEND) = 1
  - R: 10 (MORE) = 10
  - Y: (-1) (MONEY) = -1
- 字母列表（按系数绝对值排序）：[M(-9000), S(1000), O(-900), E(91), N(-90), R(10), D(1), Y(-1)]
首字母：S, M 不能为0。
回溯过程简述：
- 从 M 开始，系数-9000，是首字母，不能选0。尝试 M=1。当前总和 total = -9000*1 = -9000。
- 下一个 S，系数1000，是首字母，不能选0和1（1已被M用）。尝试 S=9。total = -9000 + 1000*9 = 0。
- 下一个 O，系数-900，非首字母，可尝试。但我们需要检查剪枝条件。假设我们给 O 分配一个数字 d，新的 total 为 0 + (-900)*d = -900d。剩下的未分配字母（E, N, R, D, Y）的正系数最大和是：给最大的正系数E分配最大剩余数字（比如8），贡献 918=728；加上D=17=7，R=106=60，正贡献总计约795。负系数最小和是：给N分配最小剩余数字（比如0），贡献-900=0；Y分配最小剩余数字（比如2），贡献-1*2=-2，负贡献总计-2。newTotal 可能的范围大约是 [-900d+795, -900d-2]。我们需要这个范围包含0。当d=0时，范围是[795, -2]（不包含0，下限>0）。实际上，d必须为1，newTotal范围是[-105, -902]（不包含0）。但我们可以继续搜索，因为剪枝计算的是精确的剩余数字，这里只是示意。在实际算法中，会计算出剩下数字的最大/最小可能组合来精确判断。
- 最终，算法会搜索到正确的分配：M=1, S=9, O=0, E=5, N=6, D=7, R=8, Y=2。

第四步：算法总结

预处理：提取字母，计算每个字母的权重系数，记录首字母限制。
排序：将字母按系数绝对值降序排列，以优化搜索顺序。
DFS回溯：
- 为当前字母尝试所有可用数字（考虑首字母限制）。
- 在每次尝试赋值时，计算当前总和 total。
- 应用可行性剪枝：计算剩余未分配字母，在最优情况下（使总和逼近0）是否能满足条件。即，计算剩余正系数字母用最大剩余数字能得到的最大正贡献 max_pos，剩余负系数字母用最小剩余数字能得到的最小负贡献 min_neg。如果当前 total + max_pos < 0 或 total + min_neg > 0，则剪枝。
- 如果所有字母分配完毕，检查总和是否为0。
返回结果：如果找到一种分配则返回 true，否则返回 false。

这个算法的核心思想是将字母算术问题转化为带有约束的数字分配问题，并通过系数权重排序和前瞻性剪枝来大幅减少搜索空间，使其在约束下可解。

LeetCode 1307. 口算难题题目描述给你一个方程，用字符串数组 words 表示一个单词的列表，用字符串 result 表示结果。如果这个方程可解，返回 True ，否则返回 False 。每个单词 words[i] 和 result 都被转换成十进制数，规则是：每个字母映射到一个数字（0-9），不同的字母不能映射到相同的数字，并且每个 words[i] 和 result 不能有前导零（即，每个单词的第一个字符不能映射到0）。如果映射后， sum(words[i]) = result 成立，则方程可解。例如：输入： words = ["SEND","MORE"], result = "MONEY" 输出： true 解释：我们可以将字母映射为： S->9, E->5, N->6, D->7, M->1, O->0, R->8, Y->2 那么 "SEND" = 9567, "MORE" = 1085, 和为 10652。 "result" = "MONEY" = 10652，所以返回 true。这是一个典型的字母算术谜题，也称为密码算术。解题核心是回溯 + 剪枝。解题过程这个问题本质上是为不同的字母分配不同的数字（0-9），使得算式成立。由于字母种类通常最多10个，直接尝试所有排列（10! ≈ 3.6百万）是可行的，但需要高效的剪枝。我们可以用列竖式的方法，从低位到高位逐列计算，并在过程中利用进位进行剪枝。第一步：问题建模与数据准备收集所有出现的字母：从 words 和 result 中提取所有不同的字母。如果字母种类超过10，直接返回 false ，因为10个数字无法分配给超过10个字母。建立权重系统：我们需要知道每个字母在最终算式“数值”中的权重（即，它是“个位”、“十位”还是“百位”？）。算式是： sum(words) = result 。我们可以转化为： sum(words) - result = 0 。更巧妙的方法是，为每个字母分配一个系数（权重）：对于 words 中的每个单词，字母出现在第 k 位（从右往左，个位为0），它的系数就加 10^k 。对于 result 中的每个字母，出现在第 k 位，它的系数就减 10^k 。最终，我们希望找到一个数字到字母的映射，满足：对所有字母的 (系数 * 分配的数字)求和等于 0。标记首字母不能为零：记录哪些字母是任何单词或结果的首字母，它们不能映射到0。第二步：回溯算法设计我们用一个 map （或数组）记录字母到数字的映射，用一个 used 数组记录数字是否已被使用。从权重最高的字母开始尝试分配数字，可以更快地触发剪枝。然而，更经典的回溯方式是为每个位置（列）进行搜索，模拟竖式加法。这里我们讲解基于系数的回溯方法，因为它更直观且易于实现剪枝。预处理：计算出每个字母的系数（一个整数值，可正可负）。收集所有需要分配数字的唯一字母列表。将字母列表按照系数的绝对值从大到小排序。这样优先处理权重大的字母，可以让总和更快地偏离0，从而尽早剪枝。记录首字母限制。深度优先搜索（DFS）：状态：当前搜索到第几个字母（ index ），当前所有已分配字母的加权和（ total ），以及当前的数字使用情况。递归基：如果 index 等于字母列表的长度，说明所有字母都已分配。检查 total 是否为0，是则返回 true ，否则返回 false 。选择列表：数字0-9，但需满足：数字未被使用；如果是首字母，则不能为0。剪枝策略：这是算法的关键！在尝试为当前字母 char 分配数字 digit 时，我们计算新的总和 newTotal = total + coeff[char] * digit 。我们可以提前计算剩下未分配的字母，它们能提供的最大正贡献和最小负贡献（基于系数和剩余可用数字）。如果即使我们给所有正系数字母分配尽可能大的剩余数字，给所有负系数字母分配尽可能小的剩余数字， newTotal 仍然大于0，那么后续无论如何分配都无法使总和归零。同理，如果即使我们给所有正系数字母分配尽可能小的剩余数字，给所有负系数字母分配尽可能大的剩余数字， newTotal 仍然小于0，也无法归零。这两种情况都可以直接剪枝。第三步：举例说明（SEND + MORE = MONEY）字母与系数（从右向左，个位权重为1）：个位列：D + E = Y + carry0 (进位初始0)。但我们用统一系数法：对于 SEND ：S(1000), E(100), N(10), D(1) 对于 MORE ：M(1000), O(100), R(10), E(1) 对于 MONEY ：M(-10000), O(-1000), N(-100), E(-10), Y(-1) 合并系数： M: 1000 (MORE) + (-10000) (MONEY) = -9000 O: 100 (MORE) + (-1000) (MONEY) = -900 S: 1000 (SEND) = 1000 E: 100 (SEND) + 1 (MORE) + (-10) (MONEY) = 91 N: 10 (SEND) + (-100) (MONEY) = -90 D: 1 (SEND) = 1 R: 10 (MORE) = 10 Y: (-1) (MONEY) = -1 字母列表（按系数绝对值排序）：[ M(-9000), S(1000), O(-900), E(91), N(-90), R(10), D(1), Y(-1) ] 首字母： S , M 不能为0。回溯过程简述：从 M 开始，系数-9000，是首字母，不能选0。尝试 M=1 。当前总和 total = -9000*1 = -9000 。下一个 S ，系数1000，是首字母，不能选0和1（1已被M用）。尝试 S=9 。 total = -9000 + 1000*9 = 0 。下一个 O ，系数-900，非首字母，可尝试。但我们需要检查剪枝条件。假设我们给 O 分配一个数字 d ，新的 total 为 0 + (-900)*d = -900d 。剩下的未分配字母（E, N, R, D, Y）的正系数最大和是：给最大的正系数E分配最大剩余数字（比如8），贡献 91 8=728；加上D=1 7=7，R=10 6=60，正贡献总计约795。负系数最小和是：给N分配最小剩余数字（比如0），贡献-90 0=0；Y分配最小剩余数字（比如2），贡献-1* 2=-2，负贡献总计-2。 newTotal 可能的范围大约是 [-900d+795, -900d-2] 。我们需要这个范围包含0。当 d=0 时，范围是[ 795, -2]（不包含0，下限>0）。实际上， d 必须为1， newTotal 范围是[ -105, -902 ]（不包含0）。但我们可以继续搜索，因为剪枝计算的是精确的剩余数字，这里只是示意。在实际算法中，会计算出剩下数字的最大/最小可能组合来精确判断。最终，算法会搜索到正确的分配：M=1, S=9, O=0, E=5, N=6, D=7, R=8, Y=2。第四步：算法总结预处理：提取字母，计算每个字母的权重系数，记录首字母限制。排序：将字母按系数绝对值降序排列，以优化搜索顺序。 DFS回溯：为当前字母尝试所有可用数字（考虑首字母限制）。在每次尝试赋值时，计算当前总和 total 。应用可行性剪枝：计算剩余未分配字母，在最优情况下（使总和逼近0）是否能满足条件。即，计算剩余正系数字母用最大剩余数字能得到的最大正贡献 max_pos ，剩余负系数字母用最小剩余数字能得到的最小负贡献 min_neg 。如果当前 total + max_pos < 0 或 total + min_neg > 0 ，则剪枝。如果所有字母分配完毕，检查总和是否为0。返回结果：如果找到一种分配则返回 true ，否则返回 false 。这个算法的核心思想是将字母算术问题转化为带有约束的数字分配问题，并通过系数权重排序和前瞻性剪枝来大幅减少搜索空间，使其在约束下可解。