用C++讲讲 LeetCode 1307 的最佳思路
LeetCode 1307「Verbal Arithmetic Puzzle」（文字算式）是一道 Hard 题，本质是约束满足问题：给一组单词表示的加法等式（比如 “SEND” + “MORE” == “MONEY”），要给每个不同的字母分配一个 0-9 的数字（同一字母同一个数字，不同字母不同数字，多位数的首字母不能是 0），判断是否存在合法分配让等式成立。最朴素的想法是暴力枚举字母到数字的排列（最多 10 个不同字母，10! 约 362 万种排列），但更好的思路是把问题转化成一个「线性方程」，再用回溯配合数值剪枝，这样能把搜索空间砍掉绝大部分。
关键的转化点在于：等式两边可以合并成一个关于字母系数的线性组合。比如某个字母在加数里的第 k 位（从右往左，个位是第 0 位）出现，就给它的系数加上 10^k；如果这个字母出现在结果（等号右边）的第 k 位，就给它的系数减去 10^k。这样整个等式 “SEND + MORE = MONEY” 就变成了 sum(coeff[letter] * digit[letter]) == 0 这一个方程，问题转化为「给每个字母分配不同数字，使这个加权和为 0」，这样就不用关心具体是哪个单词的哪一位了，统一变成一个数值约束问题。
class Solution {
public:
bool isSolvable(vector<string>& words, string result) {
vector<int> coeff(26, 0);
vector<bool> nonZero(26, false); // 多位数的首字母不能取 0
auto addWord = [&](const string& w, int sign) {
int p = 1;
for (int i = (int)w.size() - 1; i >= 0; --i) {
coeff[w[i] - 'A'] += sign * p;
p *= 10;
}
if (w.size() > 1) nonZero[w[0] - 'A'] = true;
};
for (auto& w : words) addWord(w, 1);
addWord(result, -1); // 结果这边符号取反
vector<int> letters;
for (int c = 0; c < 26; ++c) if (coeff[c] != 0) letters.push_back(c);
if (letters.size() > 10) return false; // 字母种类超过 10 个，无解
// 系数绝对值大的字母先分配，剪枝效果更好
sort(letters.begin(), letters.end(), [&](int a, int b) {
return abs(coeff[a]) > abs(coeff[b]);
});
int m = letters.size();
vector<long long> suffixMaxAbs(m + 1, 0); // 后缀系数绝对值之和的上界
for (int i = m - 1; i >= 0; --i)
suffixMaxAbs[i] = suffixMaxAbs[i + 1] + (long long)abs(coeff[letters[i]]) * 9;
vector<bool> usedDigit(10, false);
function<bool(int, long long)> dfs = [&](int idx, long long curSum) -> bool {
if (idx == m) return curSum == 0;
if (llabs(curSum) > suffixMaxAbs[idx]) return false; // 剩下的字母无论怎么取都拉不回 0，剪枝
int letter = letters[idx];
for (int d = 0; d <= 9; ++d) {
if (usedDigit[d]) continue;
if (d == 0 && nonZero[letter]) continue;
usedDigit[d] = true;
if (dfs(idx + 1, curSum + (long long)coeff[letter] * d)) {
usedDigit[d] = false;
return true;
}
usedDigit[d] = false;
}
return false;
};
return dfs(0, 0);
}
};
这个解法有两个关键的优化点值得展开讲。第一是把问题从「按单词、按位置」的复杂结构，压缩成「每个字母一个系数」的一维线性方程，这一步转化之后回溯只需要处理最多 10 个字母，逻辑变得非常干净，不用在 DFS 里同时追踪每一位的进位。第二是剪枝：给字母按系数绝对值从大到小排序后优先分配，这样错误的分配能更早被发现（系数大的字母对总和影响也大，早点定下来能更快判断某条分支走不通）；同时用 suffixMaxAbs 预计算「剩余未分配字母无论怎么取，加权和的绝对值上限是多少」，如果当前累积和的绝对值已经超过这个上限，说明剩下的字母无论怎么分配都不可能把总和拉回 0，直接剪掉这条分支，不用继续往下搜。
复杂度上，最坏情况下仍然是指数级的（最多 10 个字母全排列，约 10! 次尝试），但因为有系数剪枝，实际运行中大部分不合法的分支会在很浅的深度就被剪掉，实测效率比朴素的「枚举全部排列再逐个验证等式」快很多，能稳定通过 LeetCode 的时间限制。
如果不追求最优只想先写一版能过的暴力解，也可以直接用 next_permutation 枚举 0-9 的排列，取前 letters.size() 个数字依次赋给字母，再把每个单词按位数还原成数值验证等式是否成立，这种写法更直观好懂，缺点是没有剪枝，纯粹靠排列个数少（最多 10 个字母）撑过去，代码量更小但效率明显不如上面这版，适合先写出来保底再优化。