সাবসেক্সেন্স লাইটকোড সলিউশন  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক ব্লুমবার্গ ফেসবুক গুগল মাইক্রোসফট পিন্টারেস্ট ইয়ানডেক্স
আলগোরিদিম আইনসংগ্রহ ডায়নামিক প্রোগ্রামিং লোভী সাক্ষাত্কার সাক্ষাৎকারের প্রস্তুতি লেটকোড LeetCodeSolutions স্ট্রিং

সমস্যা বিবৃতি  

এই সমস্যায় আমাদের দুটি আলাদা দেওয়া হয় স্ট্রিং। লক্ষ্যটি প্রথম স্ট্রিংটি একটি কিনা তা খুঁজে বের করা অনুচ্ছেদ দ্বিতীয়।

উদাহরণ

first string = "abc"
second string = "mnagbcd"
true
first string = "burger"
second string = "dominos"
false

সাবসেক্সেন্স লাইটকোড সলিউশনপিন

পন্থা (পুনরাবৃত্তি)  

এটি সহজেই দেখা যায় যে আমরা তাদের প্রান্ত থেকে স্ট্রিংগুলি মেলাতে শুরু করতে পারি। যদি স্ট্রিংয়ের শেষের অক্ষরগুলি মিলে যায় তবে আমাদের দুটি স্ট্রিং যা মূলগুলি থেকে প্রাপ্ত হতে পারে তা খুঁজে পাওয়ার আমাদের সমস্যা হ্রাস পেয়েছে পরে তাদের শেষ অক্ষরগুলি বাদ দেওয়া অনুচ্ছেদের মানদণ্ড অনুসরণ করে। যদি শেষ অক্ষরগুলি মেলে না, তবে এটির জন্য অনুসন্ধান করার জন্য আমরা কেবল দ্বিতীয় স্ট্রিংয়ের শেষ অক্ষরটি ফেলে রাখি।

প্রতিটি পুনরাবৃত্তির কলগুলিতে অক্ষরগুলির তুলনা করার জন্য প্যারামিটার হিসাবে স্ট্রিংয়ের সূচকগুলি পাস করার মাধ্যমে এটি পুনরাবৃত্তভাবে করা যেতে পারে।

অ্যালগরিদম

  1. সূচক প্রথম স্ট্রিংয়ের শেষ সূচকটি চিহ্নিত করে এবংপুনরাবৃত্তির কলগুলিতে দ্বিতীয় স্ট্রিংয়ের শেষ সূচককে বোঝায়
  2. If আমি == -1:
    1. আমরা প্রথম স্ট্রিংটি পুরোপুরি অতিক্রম করেছি, ফিরে আসি সত্য
  3. If j == -1:
    1. আমরা প্রথম স্ট্রিংটি পুরোপুরি অতিক্রম করেছি, ফিরে আসি মিথ্যা
  4. If প্রথম_আরক্ষ [i] == সেকেন্ড_স্ট্রিং [জে]:
    1. সূচকগুলি সহ পুনরাবৃত্তি ফাংশন কল করুন (আমি - 1, জে - 1)
  5. সূচকগুলির সাথে পুনরাবৃত্ত ফাংশনের ফলাফলটি ফিরিয়ে দিন (i, j - 1)

ইস সাবসেক্সেন্স লেটকোড সলিউশন এর বাস্তবায়ন

সি ++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

string S , T;

bool checkSubsequence(int i , int j)
{
    if(i == -1)
        return true;
    if(j == -1)
        return false;
    if(S[i] == T[j])
        return checkSubsequence(i - 1 , j - 1);
    return checkSubsequence(i , j - 1);
}

bool isSubsequence(string s, string t)
{
    S = s , T = t;
    return checkSubsequence((int)s.size() - 1 , (int)t.size() - 1);
}

int main()
{
    string s = "abc";
    string t = "mnagbcd";

    cout << (isSubsequence(s , t) ? "true" : "false") << '\n';
    return 0;
}

জাভা প্রোগ্রাম

class is_subsequence
{
    static String S , T;

    public static void main(String args[])
    {
        String a = "abc" , b = "mnagbcd";
        System.out.println((isSubsequence(a , b) ? "true" : "false"));
    }

    static boolean checkSubsequence(int i , int j)
    {
        if(i == -1)
            return true;
        if(j == -1)
            return false;
        if(S.charAt(i) == T.charAt(j))
            return checkSubsequence(i - 1 , j - 1);
        return checkSubsequence(i , j - 1);
    }

    static boolean isSubsequence(String s, String t)
    {
        S = s;
        T = t;
        return checkSubsequence((int)s.length() - 1 , (int)t.length() - 1);
    }
}
true

জটিলতা বিশ্লেষণ ইজ সাবসেক্সেন্স লেটকোড সলিউশন

সময় জটিলতা

ও (মিনিট (এন, এম)) যেহেতু আমাদের দুটি স্ট্রিং বিপর্যস্ত না হওয়া অবধি পুনরুক্তি করা দরকার। N এবং M স্ট্রিং দৈর্ঘ্য হয়।

আরো দেখুন
এন-থ্রি ট্রাইবোনচি নম্বর লেটকোড সমাধান

স্পেস জটিলতা ity

ও (মিনিট (এম, এন) পুনরাবৃত্তি কল কারণে সবচেয়ে খারাপ ক্ষেত্রে।

পদ্ধতির (দ্বি-পয়েন্টার)  

আমরা উপরোক্ত কৌশলটি পুনরায় দুটি পয়েন্টার বজায় রেখে ব্যবহার করতে পারি i এবং সংশ্লিষ্ট স্ট্রিংয়ের শেষ সূচকগুলি সঞ্চয় করতে। তাদের দুজনের শূন্য না হওয়া পর্যন্ত আমরা পুনরাবৃত্তি করতে পারি। যদি i (প্রথম স্ট্রিংয়ের পয়েন্টার) 0 এর চেয়ে বড় বা সমান, আমরা প্রথম স্ট্রিংটি সম্পূর্ণরূপে অতিক্রম করতে সক্ষম হইনি, এবং এটি, এটি দ্বিতীয়টির অনুচ্ছেদ নয়। অন্যথায়, আমরা সত্য ফিরে।

অ্যালগরিদম

  1. দুটি পয়েন্টার শুরু করুন i এবং j উভয় স্ট্রিংয়ের শেষ সূচকগুলি সংরক্ষণ করে।
  2. যদিও i> = 0 এবং জে> = 0:
    1. যদি প্রথম_আরক্ষ [i] == সেকেন্ড_স্ট্রিং [জে]:
      1. i-, j-
    2. আর
      1. j-
  3. If i > = 0:
    1. প্রত্যাবর্তন মিথ্যা
  4. প্রত্যাবর্তন সত্য

ইস সাবসেক্সেন্স লেটকোড সলিউশন এর বাস্তবায়ন

সি ++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

string S , T;

bool isSubsequence(string s , string t)
{
    int i = s.size() , j = t.size();

    i-- , j--;

    while(i >= 0 && j >= 0)
    {
        if(s[i] == t[j])
            i-- , j--;
        else
            j--;
    }

    if(i >= 0)
        return false;
    return true;
}

int main()
{
    string s = "abc";
    string t = "mnagbcd";

    cout << (isSubsequence(s , t) ? "true" : "false") << '\n';
    return 0;
}

জাভা প্রোগ্রাম

class is_subsequence
{
    static String S , T;

    public static void main(String args[])
    {
        String a = "abc" , b = "mnagbcd";
        System.out.println((isSubsequence(a , b) ? "true" : "false"));
    }

    static boolean isSubsequence(String s , String t)
    {
        int i = s.length() , j = t.length();

        i--;
        j--;

        while(i >= 0 && j >= 0)
        {
            if(s.charAt(i) == t.charAt(j))
            {
                i--;
                j--;
            }
            else
                j--;
        }

        if(i >= 0)
            return false;
        return true;
    }
}
true

জটিলতা বিশ্লেষণ ইজ সাবসেক্সেন্স লেটকোড সলিউশন

সময় জটিলতা

ও (মিনিট (এম, এন)) আমরা যতক্ষণ না পুনরাবৃত্তি করা i বা j শূন্য হয়ে যায়। এম এবং এন স্ট্রিংগুলির দৈর্ঘ্য।

স্পেস জটিলতা ity

ও (1) যেহেতু আমরা স্মৃতিতে স্থির স্থান ব্যবহার করি।

1