ধরি একটি নতুন এলিয়েন ভাষা আছে যা ল্যাটিন অ্যালফাবেট ব্যবহার করে। কিন্তু অক্ষরগুলোর ক্রম অজানা। আমাদের ডিকশনারি থেকে নন-এম্পটি শব্দগুলোর একটি তালিকা দেওয়া আছে, যেগুলো এই নতুন ভাষার নিয়ম অনুযায়ী লেক্সিকোগ্রাফিক্যালি সর্টেড। আমাদের এই ভাষার অক্ষরগুলোর ক্রম বের করতে হবে।
উদাহরণস্বরূপ, ইনপুট ["wrt","wrf","er","ett","rftt"] হলে আউটপুট হবে "wertf"।
সমাধানের ধাপসমূহ
- দুটি ম্যাপ
degreeএবংgraphসংজ্ঞায়িত। - n := words.size()
- সব শব্দের সব ক্যারেক্টারের জন্য degree[c] = 0
- i = 0 থেকে n-2:
- l := min(words[i].size(), words[i+1].size())
- j = 0 থেকে l-1:
- x := words[i][j], y := words[i+1][j]
- যদি x != y:
- graph[x].push_back(y)
- degree[y]++
- ব্রেক
- ret := খালি স্ট্রিং
- একটি কিউ
q - degree-র সব key-value জন্য যদি value == 0: q.push(key)
- যখন q খালি না:
- x := q.front(); q.pop()
- ret += x
- graph[x]-র সব sit জন্য:
- degree[sit]--
- যদি degree[sit] == 0: q.push(sit)
- ফেরত: (ret.size() == degree.size() ? ret : "")
প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string alienOrder(vector& words) {
map degree;
map> graph;
int n = words.size();
for (int i = 0; i < words.size(); i++) {
for (int j = 0; j < words[i].size(); j++) {
degree[words[i][j]] = 0;
}
}
for (int i = 0; i < n - 1; i++) {
int l = min((int)words[i].size(), (int)words[i + 1].size());
for (int j = 0; j < l; j++) {
char x = words[i][j];
char y = words[i + 1][j];
if (x != y) {
graph[x].push_back(y);
degree[y]++;
break;
}
}
}
string ret = "";
queue q;
map::iterator it = degree.begin();
while (it != degree.end()) {
if (it->second == 0) {
q.push(it->first);
}
it++;
}
while (!q.empty()) {
char x = q.front();
q.pop();
ret += x;
vector::iterator sit = graph[x].begin();
while (sit != graph[x].end()) {
degree[*sit]--;
if (degree[*sit] == 0) {
q.push(*sit);
}
sit++;
}
}
return ret.size() == degree.size() ? ret : "";
}
};
int main() {
Solution ob;
vector v = {"wrt","wrf","er","ett","rftt"};
cout << (ob.alienOrder(v));
}
ইনপুট
{"wrt","wrf","er","ett","rftt"}
আউটপুট
wertf
