感谢 https://www.acwing.com/solution/LeetCode/content/7323/ 题解提供思路
题目描述
给你一个方程，左边用 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
算法1
这里参考了其他大佬的思路 然后自己完成的。
效果还是不太理想 只能说子路是正确的 最后的实现磕磕碰碰效率还比较低。也算是ac了吧
思路如下 强行的暴力DFS每个字母替代的数字肯定是TLE的
那么每次将每列的数字替换后，计算下将该列所有数字相加是否与result对应的字母冲突，就能减少不少不必要的计算.
使用了两个变量 map<char, int> letterMapNum; map<int, int> usedNum;
记录 字母替换了那些数字 和那些数字被使用了
还计算出字符串的最大长度 以便确定需要循环的边界 (全部按照最大长度来循环的话 还要识别部分短的字符串是否越界)
剩下的就是DFS 遍历替换和CHECK最后字母替换数字是否正确
C++ 代码
class Solution {
public:
map<char, int> letterMapNum;
map<int, int> usedNum;
int maxStringLen = 0;
int GetmaxStringLen(const vector<string>& words)
{
int ret = 0;
for (auto& e : words) {ret = max((int)e.size(), ret);}
return ret;
}
bool Check(const vector<string>& words, const string& result)
{
int sum = 0; int tn = 0;
for (int i = 0; i < words.size(); i++) {
string s = words[i];
reverse(s.begin(), s.end());
tn = 0;
for (int j = 0; j < s.size(); j++) {
int num = letterMapNum[s[j]];
tn = tn * 10 + num;
}
sum += tn;
}
string s;
while (sum != 0) {
int e = sum % 10;
sum = sum / 10;
if (usedNum[e] == 0) {s += "?";}
else {
for (auto& ele : letterMapNum) {
if (ele.second == e) {
s += ele.first;
break;
}
}
}
}
if (s.size() != result.size()) return false;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '?' ) {
char c = result[i];
if (letterMapNum[c] != -1)return false;
}
else if (s[i] != result[i]) {return false;}
}
return true;;
}
bool Dfs(int x,int y , int sum ,const vector<string>& words,const string& result)
{
bool ret = false;
if (x == words.size() && y == maxStringLen) {
//ret = check
ret = Check(words, result);
return ret;
}
if (x>= words.size() ) {
//检测上一列的和是否符合要求
int resultC = result[y];
if (letterMapNum[resultC] != -1 && letterMapNum[resultC] != sum % 10) return false;
//该列的和变成下一列的进位
sum = sum / 10;
//计算下一列所有字母的和
x = 0; y++;
}
if (y < words[x].size()) {
char c = words[x][y];
if (letterMapNum[c] != -1) {
//已经将该字母替换
sum += letterMapNum[c];
if (y == words[x].size() - 1 && letterMapNum[c] == 0) {return false;}
if (Dfs(x + 1, y, sum, words, result)) return true;
}
else {
//没有将该字母替换
int start = 0;
if (y == words[x].size() - 1) start = 1;
for (int i = start; i <= 9; i++) {
if (usedNum[i] != 0) continue;
int oldsum = sum; int oldmap = letterMapNum[c];int oldUsed = usedNum[i];
usedNum[i] = 1; letterMapNum[c] = i;
sum += i;
if (Dfs(x + 1, y, sum, words, result)) return true;
sum = oldsum; letterMapNum[c] = oldmap; usedNum[i] = oldUsed;
}
}
}
else {
if (Dfs(x + 1, y, sum, words, result)) return true;
}
return false;
}
bool isSolvable(vector<string>& words, string result) {
bool ret = false;
for (int i = 0; i < words.size(); i++) reverse(words[i].begin(), words[i].end());
reverse(result.begin(), result.end());
maxStringLen = GetmaxStringLen(words);
if (result.size() > (maxStringLen + 1)) return ret;
for (int i = 0; i < 26; i++) {char a = 'A';a += i;letterMapNum[a] = -1;}
ret = Dfs(0,0,0, words, result);
return ret;
}
};
