روز 38 – دیکشنری بیگانه

هی همه! به روز دیگری از حل مسئله خوش آمدید. امروز روز 38 است، و من همچنان به تلاش خود برای ثبات ادامه می دهم. امروز ما با یک مشکل جالب روبرو هستیم. اما قبل از شیرجه رفتن، مطمئن شویم که همه در یک صفحه هستیم.

اگر با مرتب‌سازی توپولوژیکی در نمودارها آشنا نیستید، پیشنهاد می‌کنم مقاله قبلی 37 را بخوانید تا کار پشت مرتب‌سازی توپولوژیکی را درک کنید.

یک فرهنگ لغت مرتب شده از یک زبان بیگانه با N کلمه و k الفبای شروع فرهنگ لغت استاندارد ارائه شده است. ترتیب کاراکترها را در زبان بیگانه پیدا کنید.

توجه: ممکن است بسیاری از سفارش‌ها برای یک مورد آزمایشی خاص امکان‌پذیر باشد، بنابراین شما می‌توانید هر ترتیب معتبری را برگردانید و خروجی 1 خواهد بود اگر ترتیب رشته برگشتی توسط تابع درست باشد، در غیر این صورت 0 نشان دهنده رشته نادرست برگردانده شده است.

مثال 1:

• ورودی:
• N = 5، K = 4
• dict = {“baa”, “abcd”، “abca”، “cab”، “cad”}
• خروجی: 1
• توضیح: در اینجا ترتیب کاراکترها ‘b’، ‘d’، ‘a’، ‘c’ است توجه داشته باشید که کلمات مرتب شده اند و در زبان داده شده “baa” قبل از “abcd” می آید، بنابراین “b” قبل از “a” است. در خروجی

مثال 2:

• ورودی:
• N = 3، K = 3
• dict = {“caa”, “aaa”, “aab”}
• خروجی: 1
• توضیح: در اینجا ترتیب کاراکترها ‘c’، ‘a’، ‘b’ است توجه داشته باشید که کلمات مرتب شده اند و در زبان داده شده “caa” قبل از “aaa” می آید، بنابراین “c” قبل از “a” در خروجی است.

محدودیت ها:

• 1 ≤ N، M ≤ 300
• 1 ≤ K ≤ 26
• 1 ≤ طول کلمات ≤ 50

بینش:

بیایید ابتدا با تجزیه سوال شروع کنیم.
به ما یک فرهنگ لغت جدید داده شده است که در آن ترتیب حروف الفبا مانند فرهنگ لغت انگلیسی ما نیست.
ترتیب کاراکتر را به صورت ‘a’ -> ‘b’ -> ‘c’………->’z’ دنبال می کنیم.
یک فرهنگ لغت جدید به ما داده شده است و باید ترتیب کاراکترهای آن را پیدا کنیم. برای کمک به ما، آنها به ما گفته اند که فرهنگ لغت مرتب شده است (همانطور که باید باشد) به این معنی است که اگر بتوانیم کاراکترها را از یک کلمه به کلمه بعدی آن متمایز کنیم، می توانیم یک چیز را پیدا کنیم، که در آن ترتیب خاص اول می شود.

بیایید ابتدا یک مثال را بررسی کنیم.

در مثال 1 بگویید: baa قبل از abcd می آید.
اگر هر دو کلمه را کاراکتر به نویسه مقایسه کنیم، می توانیم از مشاهدات خود دریافت کنیم که “b” قبل از “a” قرار می گیرد. بنابراین ما آن را ذخیره می کنیم.
در مرحله بعد، اگر «abcd» را بررسی کنیم قبل از «abca» آمده است، بنابراین «d» > «a».
به همین ترتیب وقتی جلوتر می‌رویم، “a” > “c” می‌گیریم

سفارش ما در پایان این خواهد بود:
‘b’ -> ‘d’ -> ‘a’ -> ‘c’

از این رو می‌توانیم ببینیم که مانند مرتب‌سازی توپولوژیکی است که یکی باید قبل از دیگری قرار گیرد. در پایان باید ترتیب آن نمودار را برگردانیم. ما می توانیم آن را در اینجا اعمال کنیم.

الگوریتم:

سلام! بیایید به الگوریتم حل مسئله در دست شیرجه بزنیم. برای ایجاد لیست مجاورت برای نمودار و انجام مرتب‌سازی توپولوژیک، باید چند مرحله را دنبال کنیم. من مراحل را برای شما شرح می دهم:

مرحله 1: ایجاد لیست مجاورت

• ما با اجرای یک حلقه از شاخص شروع تا دومین شاخص آخر شروع می کنیم. این به ما این امکان را می دهد که شاخص فعلی (بیایید آن را s1 بنامیم) و شاخص بعدی (s2) را بررسی کنیم.
• در داخل این حلقه، ما دو کلمه را با هم مقایسه خواهیم کرد: کلمه در شاخص فعلی (s1) و کلمه در شاخص بعدی (s2). برای مقایسه آنها، یک حلقه دیگر تا طول رشته کوچکتر اجرا می کنیم.
• در این حلقه دوم، اگر هر گونه نابرابری را در یک شاخص خاص پیدا کنیم (s1[i] != s2[i]، آنها را به عنوان لبه از s1 به لیست مجاورت اضافه می کنیم[i] به s2[i]، آنها را به عنوان اعداد در نظر بگیرید (با کم کردن “a” از آنها). هنگامی که این شخصیت متفاوت را پیدا کردیم، بلافاصله از حلقه خارج خواهیم شد.
• این فرآیند به ما امکان می دهد اولین کاراکتر متمایز کننده رشته های مجاور را پیدا کرده و نمودار را ایجاد کنیم. بنابراین در پایان این مرحله، لیست مجاورت خود را آماده خواهیم کرد.

مرحله 2: مرتب سازی توپولوژیکی

• در ادامه، درجه هر گره را در نمودار محاسبه کرده و در یک آرایه درجه بندی ذخیره می کنیم. ما می توانیم از طریق لیست مجاورت تکرار کنیم و برای هر گره u->v، درجه v را 1 در آرایه indegree افزایش می دهیم.
• در ابتدا، همیشه حداقل یک گره با درجه 0 وجود خواهد داشت. ما چنین گره هایی را در یک صف قرار می دهیم.
• در مرحله بعد، شروع به بیرون زدن گره ها از صف می کنیم. برای هر گره باز شده، آن را به آرایه پاسخ خود اضافه می کنیم. سپس، برای تمام گره های مجاور آن، درجه آنها را 1 در آرایه درجه کاهش می دهیم. به عنوان مثال، اگر گره u (از صف بیرون آمده) یک یال به سمت گره v (u->v) داشته باشد، درجه را کاهش می دهیم.[v] توسط 1.
• اگر پس از کاهش درجه، درجه هر گره صفر شود، آن گره را دوباره به صف می بریم.
• ما این مراحل را تا زمانی که صف کاملاً خالی شود، تکرار می‌کنیم، و مطمئن می‌شویم که کل نمودار را به روشی Breadth-First Search (BFS) طی می‌کنیم. در پایان، ترتیب خطی گره ها را در آرایه پاسخ خود خواهیم داشت.

مرحله 3: نهایی کردن پاسخ

• در نهایت، برای به دست آوردن پاسخ نهایی، عناصر موجود در آرایه پاسخ را تکرار می کنیم. ما هر عنصر را به یک رشته نهایی اضافه می کنیم و با افزودن “a” به هر یک از آنها، آن را به یک کاراکتر تبدیل می کنیم.
• پس از این تکرار، رشته نهایی خود را آماده خواهیم کرد.
• ما می توانیم این رشته را به عنوان پاسخ نهایی خود برگردانیم و مشکل موجود را حل کنیم.
• خودشه! پس از این مراحل، می‌توانیم لیست مجاورت را ایجاد کنیم، با استفاده از BFS مرتب‌سازی توپولوژیکی را انجام دهیم و پاسخ نهایی را به صورت رشته به دست آوریم. امیدوارم این تفکیک به شما در درک بهتر الگوریتم کمک کند.

کد:

// User function Template for C++

class Solution{
    public:
    vector<int> topoSort(int V, vector<int> adj[]) 
    {
       vector<int> indegree(V,0);
       for(int i = 0; i < V; i++){
           for(auto it: adj[i]){
               indegree[it]++;
           }
       }
       queue<int> q;
       for(int i = 0;  i < V; i++){
           if(indegree[i] == 0){
               q.push(i);
           }
       }
       vector<int> res;
       while(!q.empty()){
           int node = q.front();
           q.pop();
           res.push_back(node);

           for(auto it: adj[node]){
               indegree[it]--;
               if(indegree[it] == 0){
                   q.push(it);
               }
           }
       }
       return res;
    }
    string findOrder(string dict[], int N, int K) {
        vector<int> adj[K];
        //step to get adjacency list
        for(int i = 0; i < N-1; i++){
            string s1 = dict[i];
            string s2 = dict[i+1];
            int len = min(s1.size(),s2.size());
            for(int j = 0; j < len; j++){
                if(s1[j] != s2[j]){
                    adj[s1[j] - 'a'].push_back(s2[j] - 'a');
                    break;
                }
            }
        }
       vector<int> res = topoSort(K,adj);
       string ans = "";
       for(auto it : res){
           ans  = ans + char(it + 'a');
       }
       return ans;

    }
};

تحلیل پیچیدگی:

در صورت داشتن هر گونه سوال یا نیاز به توضیح بیشتر می توانید به من بگویید. حل مشکل مبارک!