作者推荐
本文涉及知识点
数学 回溯 字符串 性能优化
LeetCode1307. 口算难题
给你一个方程，左边用 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
回溯
简单的例子
AB + AC = BCD
10A+B+10A+C = 100B+10C+D
20A-99B -9C-D = 0
系数20,-99,-9,-1 放到向量v中，并排序。如果直接回溯，时间复杂度1010超时。
将v排序，从后到前处理。处理v[i]，先估算v[0,i)的最小值iMin和最大值iMax，如果已有值x+iMin > 0或 x+iMax < 0，则剪枝忽略。
求最小值：
如果存在负数，最小的负数（绝对值最大）对应最大的未选择值。如果存在正数，最大的正数取最小的未选择数。
求最大值：
如果存在负数，最小的负数（绝对值最大）对应最小的未选择值。如果存在正数，最大的正数取最大的未选择数。
代码
核心代码（超时）
class Solution { public: bool isSolvable(vector<string>& words, string result) { unordered_map<char, int> mCharCnt; unordered_map<char, bool> mCharNot0;//开头不能为0 auto Add = [&](int iMul, const string& s) { for (int i = s.length() - 1; i >= 0; i--, iMul*=10) { mCharCnt[s[i]] += iMul; } if (s.length() > 1) { mCharNot0[s[0]] = true; } }; for (const auto& s : words) { Add(1, s); } Add(-1, result); vector<pair<int,int>> v; for (const auto& [tmp, cnt] : mCharCnt) { v.emplace_back(cnt,mCharNot0[tmp]); } sort(v.begin(), v.end()); set<int> setSel; for (int i = 0; i < 10; i++) { setSel.emplace(i); } return DFS(v, setSel, 0, 0); } template<class Pr> int MinMax(const pair<int, int>*p, int n, set<int,Pr> setSel) { int result = 0; for (int i = 0; i != n;) { if (p[i].first < 0) { result += *setSel.begin()*p[i++].first; setSel.erase(setSel.begin()); } else { result += *setSel.rbegin()*p[--n].first; setSel.erase(std::prev(setSel.end())); } } return result; } bool DFS(const vector<pair<int,int>> & v, set<int>& setSel, int leve, int result) { if (v.size() == leve) { return 0 == result; } const int iMin = MinMax(v.data()+leve, v.size()-leve, set<int, std::greater<int>>(setSel.begin(), setSel.end())); const int iMax = MinMax(v.data() + leve, v.size() - leve, setSel); if ((iMin + result > 0) || (iMax + result < 0)) { return false; } for (int i = 9; i >= v[leve].second; i--) { if (!setSel.count(i)) { continue; } setSel.erase(i); if (DFS(v, setSel, leve + 1, result + v[leve].first * i)) { return true; } setSel.emplace(i); } return false; } };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<string> words; string result; { Solution sln; words = { "A","B" }, result = "A"; auto res = sln.isSolvable(words, result); Assert(true, res); } { Solution sln; words = { "CBA","CBA","CBA","CBA","CBA" }, result = "EDD"; auto res = sln.isSolvable(words, result); Assert(false, res); } { Solution sln; words = { "SEND", "MORE" }, result = "MONEY"; auto res = sln.isSolvable(words, result); Assert(true, res); } { Solution sln; words = { "SIX", "SEVEN", "SEVEN" }, result = "TWENTY"; auto res = sln.isSolvable(words, result); Assert(true, res); } { Solution sln; words = { "THIS", "IS", "TOO" }, result = "FUNNY"; auto res = sln.isSolvable(words, result); Assert(true, res); } { Solution sln; words = { "LEET", "CODE" }, result = "POINT"; auto res = sln.isSolvable(words, result); Assert(false, res); } }
估算最小值最大值
pair<int,int> MinMaxSingle(const pair<int, int>* p, int n) { int less0 = 0, more0 = 0; for (int i = 0; i < n ; i++ ) { if (p[i].first < 0) { less0 += p[i].first; } else { more0 += p[i].first; } } return { less0 * 9,more0 * 9 }; }
可以提升一倍，还是过不了。
一，for循环也可以省略。
二，向量变原生数组。
这两个方法效果很小。
class Solution { public: bool isSolvable(vector<string>& words, string result) { unordered_map<char, int> mCharCnt; unordered_map<char, bool> mCharNot0;//开头不能为0 auto Add = [&](int iMul, const string& s) { for (int i = s.length() - 1; i >= 0; i--, iMul*=10) { mCharCnt[s[i]] += iMul; } if (s.length() > 1) { mCharNot0[s[0]] = true; } }; for (const auto& s : words) { Add(1, s); } Add(-1, result); pair<int, int> v[10]; int less0 = 0, more0 = 0; for (const auto& [tmp, cnt] : mCharCnt) { v[m_c++] = { cnt,mCharNot0[tmp] }; if (cnt < 0) { less0 += cnt; } else { more0 += cnt; } } sort(v, v+m_c); set<int> setSel; for (int i = 0; i < 10; i++) { setSel.emplace(i); } return DFS(v, setSel, 0, 0,more0,less0); } bool DFS(const pair<int, int>* p, set<int>& setSel, int leve, int result,int more0,int less0) { if (m_c == leve) { return 0 == result; } if ((less0*9 + result > 0) || (more0*9 + result < 0)) { return false; } for (int i = 9; i >= p[leve].second; i--) { if (!setSel.count(i)) { continue; } setSel.erase(i); const int curLess0 = min(0, p[leve].first); const int curMore0 = max(0, p[leve].first); if (DFS(p, setSel, leve + 1, result + p[leve].first * i,more0+curMore0,less0+curLess0)) { return true; } setSel.emplace(i); } return false; } int m_c = 0; };
先处理绝对值大的
速度提升大约1000倍。
class Solution { public: bool isSolvable(vector<string>& words, string result) { unordered_map<char, int> mCharCnt; unordered_map<char, bool> mCharNot0;//开头不能为0 auto Add = [&](int iMul, const string& s) { for (int i = s.length() - 1; i >= 0; i--, iMul*=10) { mCharCnt[s[i]] += iMul; } if (s.length() > 1) { mCharNot0[s[0]] = true; } }; for (const auto& s : words) { Add(1, s); } Add(-1, result); pair<int, int> v[10]; int less0 = 0, more0 = 0; for (const auto& [tmp, cnt] : mCharCnt) { v[m_c++] = { cnt,mCharNot0[tmp] }; if (cnt < 0) { less0 += cnt; } else { more0 += cnt; } } sort(v, v + m_c, [&](const auto& pr1, const auto& pr2) {return abs(pr1.first) > abs(pr2.first); }); set<int> setSel; for (int i = 0; i < 10; i++) { setSel.emplace(i); } return DFS(v, setSel, 0, 0,more0,less0); } bool DFS(const pair<int, int>* p, set<int>& setSel, int leve, int result,int more0,int less0) { if (m_c == leve) { return 0 == result; } if ((less0*9 + result > 0) || (more0*9 + result < 0)) { return false; } for (int i = 9; i >= p[leve].second; i--) { if (!setSel.count(i)) { continue; } setSel.erase(i); const int curLess0 = min(0, p[leve].first); const int curMore0 = max(0, p[leve].first); if (DFS(p, setSel, leve + 1, result + p[leve].first * i,more0-curMore0,less0-curLess0)) { return true; } setSel.emplace(i); } return false; } int m_c = 0; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
