資料結構
網路
關係資料庫管理系統 (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 次瀏覽
