ধরি একটি সমীকরণ আছে, বাম পাশে শব্দগুলোর মাধ্যমে এক্সপ্রেশন এবং ডান পাশে ফলাফল। নিচের নিয়মানুযায়ী সমীকরণটি সমাধানযোগ্য কিনা তা যাচাই করতে হবে –
প্রতিটি ক্যারেক্টার একটি ডিজিট (0-9) হিসেবে ডিকোড হবে
বিভিন্ন ক্যারেক্টার ভিন্ন ডিজিটে ম্যাপ হবে
প্রতিটি শব্দ এবং ফলাফল একটি নম্বর হিসেবে ডিকোড হবে যেখানে লিডিং জিরো থাকবে না
বাম পাশের নম্বরগুলোর যোগফল ডান পাশের নম্বরের সমান হবে
ইনপুট যদি words = ["SEND","MORE"], result = "MONEY" হয়, তবে আউটপুট True, কারণ S→9, E→5, N→6, D→7, M→1, O→0, R→8, Y→2 ম্যাপ করলে 9567 + 1085 = 10652 হয়।
সমাধানের ধাপসমূহ
i2c (সাইজ 10), c2i (সাইজ 26), w অ্যারে সংজ্ঞায়িত করুন
solve() ফাংশন সংজ্ঞায়িত করুন যা idx, l, sum নেবে – ব্যাকট্র্যাকিং করে ডিজিট অ্যাসাইন করবে
যদি l == r.size() হয়, তবে sum == 0 কিনা চেক করুন
যদি idx == w.size() হয়, তবে রিজাল্টের করেন্ট ডিজিট চেক করুন
যদি l >= w[idx].size() হয়, তবে solve(idx+1, l, sum) কল করুন
যদি ক্যারেক্টার ইতিমধ্যে অ্যাসাইন করা থাকে, তবে সেটা ব্যবহার করুন
অন্যথায় 0-9 পর্যন্ত ডিজিট ট্রাই করুন (লিডিং জিরো এড়িয়ে)
মূল পদ্ধতিতে – i2c এবং c2i -1 দিয়ে ফিল করুন, result এবং 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
