मान लीजिए हमारे पास एक समीकरण है, बाईं ओर शब्दों द्वारा दर्शाए गए व्यंजक और दाईं ओर परिणाम। हमें जांचना है कि क्या निम्नलिखित नियमों के तहत समीकरण हल करने योग्य है या नहीं:
प्रत्येक वर्ण को एक अंक (0 से 9) के रूप में डिकोड किया जाता है।
विभिन्न वर्णों के प्रत्येक जोड़े को अलग-अलग अंकों पर मैप करना होगा।
प्रत्येक words[i] और परिणाम को एक संख्या के रूप में डिकोड किया जाता है जहां कोई अग्रणी शून्य नहीं होते।
बाईं ओर की संख्याओं का योग दाईं ओर की संख्या के बराबर होगा।
हम जांचेंगे कि समीकरण हल करने योग्य है या नहीं।
यदि इनपुट 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 के समान है।
हल करने के चरण
आकार 10 का सरणी i2c, आकार 26 का सरणी c2i, और एक सरणी w परिभाषित करें
solve() फ़ंक्शन परिभाषित करें जो idx, l, sum लेता है
यदि l == r.size() तो sum == 0 होने पर true लौटाएं
यदि idx == w.size() तो परिणाम के वर्ण की जांच करें और पुनरावर्ती कॉल करें
यदि l >= w[idx].size() तो solve(idx+1, l, sum) लौटाएं
यदि वर्ण पहले से मैप है तो मान जोड़कर पुनरावर्ती कॉल करें
अन्यथा 0-9 तक सभी अंकों को आजमाएं, बैकट्रैकिंग के साथ
मुख्य विधि से: सरणियों को -1 से भरें, परिणाम और शब्दों को उलटें, 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);
}
};
int main() {
Solution ob;
vector<string> v = {"SEND","MORE"};
cout << (ob.isSolvable(v, "MONEY"));
return 0;
}
इनपुट
{"SEND","MORE"}, "MONEY"
आउटपुट
1
