არის თანმიმდევრობის Leetcode გამოსავალი


Რთული ტური Easy
ხშირად ეკითხებიან Adobe Amazon Bloomberg Facebook Google microsoft Pinterest Yandex
დინამიური პროგრამირება ხარბ სიმებიანი

პრობლემის განცხადება

ამ პრობლემის დროს, ჩვენ ორი განსხვავებული გვეძლევა სიმები. მიზანია გაარკვიოს არის თუ არა პირველი სტრიქონი მიმდევრობა მეორის.

მაგალითები

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

არის თანმიმდევრობის Leetcode გამოსავალი

მიდგომა (რეკურსიული)

ადვილი გასაგებია, რომ ჩვენ შეგვიძლია დავიწყოთ სტრიქონების შესატყვისი მათი ბოლოებიდან. თუ სიმების ბოლო სიმბოლოები ემთხვევა, ჩვენ შემცირებული ქვეპრობლემა გვაქვს იმის დადგენისა, არის თუ არა ორი სტრიქონი, რომელთა მიღებაც შესაძლებელია ორიგინალიდან მას შემდეგ, რაც მათი ბოლო სიმბოლოების ვარდნა მიჰყევით მიმდევრობის კრიტერიუმებს. თუ ბოლო სიმბოლოები არ ემთხვევა, ჩვენ მხოლოდ მეორე სტრიქონის ბოლო სიმბოლოს ვუშვებთ მასში მოსაძებნად.

ეს შეიძლება გაკეთდეს რეკურსიულად, სტრიქონების ინდექსების პარამეტრით, როგორც სიმბოლოების შედარება თითოეულ რეკურსიულ ზარზე.

ალგორითმი

  1. ინდექსი აღნიშნავს პირველი სტრიქონის ბოლო ინდექსს დააღნიშნავს მეორე სტრიქონის ბოლო ინდექსს რეკურსიულ ზარებში
  2. If მე == -1:
    1. ჩვენ მთლიანად გადავკვეთეთ პირველი სტრიქონი, დავბრუნდეთ მართალია
  3. If კ == -1:
    1. ჩვენ მთლიანად გადავკვეთეთ პირველი სტრიქონი, დავბრუნდეთ ყალბი
  4. If first_string [i] == მეორე_სტრიქონი [j]:
    1. რეკურსიული ფუნქციების ინდექსებით დარეკვა (i - 1, j - 1)
  5. რეკურსიული ფუნქციის შედეგის ინდექსებით დაბრუნება (i, j - 1)

Implementation Leetcode Solution- ის განხორციელება

C ++ პროგრამა

#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

არის თანმიმდევრული ლეეტკოდის ამოხსნის სირთულის ანალიზი

დროის სირთულე

O (წთ (N, M)) რადგან ჩვენ უნდა განმეორდეს, სანამ რომელიმე სტრიქონი არ გადაიკვეთება. N და M სიმების სიგრძეა.

სივრცის სირთულე

O (წთ (M, N) უარეს შემთხვევაში რეკურსიული ზარების გამო.

მიდგომა (ორნიშნა)

შეგვიძლია გამოვიყენოთ ზემოხსენებული ტექნიკა, განმეორებით, ორი მაჩვენებლის შენარჩუნებით i და შესაბამისი სტრიქონების ბოლო ინდექსების შესანახად. ჩვენ შეგვიძლია განმეორება იქამდე, სანამ რომელიმე მათგანი ნულდება. თუკი i (პირველი სტრიქონის მაჩვენებელი) მეტია ან ტოლი 0-ის, ჩვენ ვერ შევძელით პირველი სტრიქონის სრულად გადალახვა და, შესაბამისად, ეს არ არის მეორე. სხვაგვარად, ჩვენ ვბრუნდებით ჭეშმარიტად.

ალგორითმი

  1. ორი მაჩვენებლის ინიცირება მე და ჯ ორივე სტრიქონის ბოლო ინდექსების შენახვა.
  2. მიუხედავად იმისა, i> = 0 და j> = 0:
    1. თუ პირველი_სტრიქონი [i] == მეორე_სტრიქონი [j]:
      1. i-, j-
    2. სხვა
      1. j-
  3. If i > = 0:
    1. დაბრუნების ყალბი
  4. დაბრუნების მართალია

Implementation Leetcode Solution- ის განხორციელება

C ++ პროგრამა

#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

არის თანმიმდევრული ლეეტკოდის ამოხსნის სირთულის ანალიზი

დროის სირთულე

O (წთ (M, N)) როგორც ჩვენ განვაგრძობთ განმეორებას მანამ, სანამ მე ან ჯ ხდება ნულოვანი. M და N სიმების სიგრძეა.

სივრცის სირთულე

O (1) რადგან მეხსიერებაში მუდმივ ადგილს ვიყენებთ.