数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++文字算术谜题
假设我们有一个方程式，等式左边用单词表示表达式，右边表示结果。我们需要检查在以下规则下该方程式是否可解：
每个字符解码为一个数字（0到9）。
每对不同的字符必须映射到不同的数字。
每个words[i]和result都解码为一个没有前导零的数字。
左边数字的和等于右边的数字。
我们将检查方程式是否可解。
因此，如果输入类似于words = ["SEND","MORE"], result = "MONEY"，则输出为True，因为当我们将字母映射如下所示：Map 'S'-> 9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0,'R'->8, 'Y'->'2'，则"SEND" + "MORE" = "MONEY" 等同于 9567 + 1085 = 10652。
为了解决这个问题，我们将遵循以下步骤：
定义一个大小为10的数组i2c，一个大小为26的数组c2i和另一个数组w。
定义一个函数solve()，它将接收idx, l, sum作为参数。
如果l等于r的大小，则：
当sum等于0时返回true。
如果idx等于w的大小，则：
如果c2i[r[l] - 'A'的ASCII码]不等于-1，则：
如果c2i[r[l] - 'A'的ASCII码]等于sum mod 10，则：
返回solve(0, l + 1, sum / 10)
否则，如果i2c[sum mod 10]等于-1，则：
如果l等于r的大小并且sum mod 10等于0，则：
返回false
c2i[r[l] - 'A'的ASCII码] = sum mod 10
i2c[sum mod 10] = r[l] - 'A'的ASCII码
temp := solve(0, l + 1, sum / 10)
c2i[r[l] - 'A'的ASCII码] = -1
i2c[sum mod 10] = -1
返回temp
返回false
如果l >= w[idx]的大小，则：
返回solve(idx + 1, l, sum)
如果c2i[w[idx, l] - 'A']不等于-1，则：
如果l等于w[idx]的大小并且c2i[w[idx, l] - 'A'的ASCII码]等于0，则：
返回false
返回solve(idx + 1, l, sum + c2i[w[idx, l] - 'A'的ASCII码])
初始化i := 0，当i < 10时，更新（i递增1），执行：
如果i2c[i]不等于-1，则：
忽略以下部分，跳到下一个迭代。
如果i等于0并且l等于w[idx]的大小，则：
忽略以下部分，跳到下一个迭代。
i2c[i] := w[idx, l] - 'A'的ASCII码
c2i[w[idx, l] - 'A'的ASCII码] = i
temp := solve(idx + 1, l, sum + i)
i2c[i] := -1
c2i[w[idx, l] - 'A'的ASCII码] = -1
如果temp不为零，则：
返回true
返回false
在主方法中执行以下操作：
用-1填充i2c和c2i。
反转数组result。
初始化i := 0，当i < words的大小，更新（i递增1），执行：
如果words[i]的大小 > result的大小，则：
返回false
反转数组words[i]
r := result, w := words
返回solve(0, 0, 0)
让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
char i2c[10];
int c2i[26];
vector<string> w;
string r;
bool solve(int idx, int l, int sum){
if (l == r.size()) {
return sum == 0;
}
if (idx == w.size()) {
if (c2i[r[l] - 'A'] != -1) {
if (c2i[r[l] - 'A'] == sum % 10) {
return solve(0, l + 1, sum / 10);
}
}
else if (i2c[sum % 10] == -1) {
if (l == r.size() - 1 && sum % 10 == 0)
return false;
c2i[r[l] - 'A'] = sum % 10;
i2c[sum % 10] = r[l] - 'A';
bool temp = solve(0, l + 1, sum / 10);
c2i[r[l] - 'A'] = -1;
i2c[sum % 10] = -1;
return temp;
}
return false;
}
if (l >= w[idx].size()) {
return solve(idx + 1, l, sum);
}
if (c2i[w[idx][l] - 'A'] != -1) {
if (l == w[idx].size() - 1 && c2i[w[idx][l] - 'A'] == 0){
return false;
}
return solve(idx + 1, l, sum + c2i[w[idx][l] - 'A']);
}
for (int i = 0; i < 10; i++) {
if (i2c[i] != -1)
continue;
if (i == 0 && l == w[idx].size() - 1)
continue;
i2c[i] = w[idx][l] - 'A';
c2i[w[idx][l] - 'A'] = i;
bool temp = solve(idx + 1, l, sum + i);
i2c[i] = -1;
c2i[w[idx][l] - 'A'] = -1;
if (temp)
return true;
}
return false;
}
bool isSolvable(vector<string>& words, string result){
memset(i2c, -1, sizeof(i2c));
memset(c2i, -1, sizeof(c2i));
reverse(result.begin(), result.end());
for (int i = 0; i < words.size(); i++) {
if (words[i].size() > result.size())
return false;
reverse(words[i].begin(), words[i].end());
}
r = result;
w = words;
return solve(0, 0, 0);
}
};
main(){
Solution ob;
vector<string> v = {"SEND","MORE"};
cout << (ob.isSolvable(v, "MONEY"));
}输入
{"SEND","MORE"}, "MONEY"输出
1
401 次浏览
