Энэ нь Дараагийн Leetcode шийдэл юм


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Bloomberg Facebook-ийн Google-ийн Microsoft- Pinterest Yandex
Динамик програмчлал Шунахай String

Асуудлын мэдэгдэл

Энэ асуудалд бид хоёр өөр зүйлийг өгдөг мөр. Зорилго нь эхний мөр нь a эсэхийг олж мэдэх явдал юм дараалал хоёр дахь.

жишээ нь

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

Энэ нь Дараагийн Leetcode шийдэл юм

Хандалт (рекурсив)

Бид мөрүүдийг төгсгөлөөс нь тааруулж эхлэх боломжтой гэдгийг харахад хялбар юм. Хэрэв мөрүүдийн сүүлчийн тэмдэгтүүд хоорондоо таарч байгаа бол эх мөрнөөс олж болох хоёр мөрийг олох дэд асуудал бидэнд багассан болно. дараа Сүүлийн тэмдэгтүүдээ хаях нь дараагийн шалгуурыг дагаж мөрддөг. Хэрэв төгсгөлийн тэмдэгтүүд хоорондоо тохирохгүй байвал бид хоёр дахь мөрийн сүүлчийн тэмдэгтийг унагаж цааш нь хайж олох хэрэгтэй.

Үүнийг рекурсив дуудлага бүрт тэмдэгтүүдийг харьцуулахын тулд мөрүүдийн индексийг параметр болгон дамжуулж рекурсив байдлаар хийж болно.

Алгоритм

  1. индекс эхний мөрийн сүүлчийн индексийг илэрхийлнэрекурсив дуудлага дахь хоёр дахь мөрийн сүүлчийн индексийг илэрхийлнэ
  2. If i == -1:
    1. Бид эхний мөрийг бүрэн туулсан, буцах үнэн
  3. If j == -1:
    1. Бид эхний мөрийг бүрэн туулсан, буцах хуурамч
  4. If эхний мөр [би] == хоёрдахь мөр [j]:
    1. рекурсив функцийг индексээр дуудах (i - 1, j - 1)
  5. Рекурсив функцийн үр дүнг индексээр буцаана (i, j - 1)

Is Subsequence Leetcode шийдлийн хэрэгжилт

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;
}

Java програм

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

Is Дараагийн Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (мин (N, M)) аль ч утсыг гатлах хүртэл бид дахин давтах хэрэгтэй. N болон M мөрүүдийн урт юм.

Сансрын нарийн төвөгтэй байдал

O (мин (M, N) рекурсив дуудлагын улмаас хамгийн муу тохиолдолд.

Хандалт (Хоёр цэг)

Бид дээрх техникийг хоёр заагчийг хадгалах замаар давтаж ашиглаж болно i болон тус тусын мөрийн сүүлийн индексийг хадгалах. Эдгээрийн аль нь ч тэг болох хүртэл бид давтаж болно. Хэрэв i (эхний мөрний заагч) нь 0-ээс их эсвэл тэнцүү, бид эхний мөрийг бүрэн гүйцэд туулж чадаагүй тул энэ нь хоёр дахь дараалал биш юм. Бусад нь бид үнэн болж эргэж ирнэ.

Алгоритм

  1. Хоёр заагчийг эхлүүлнэ үү би ба j хоёр мөрний сүүлчийн индексийг хадгалах.
  2. Хэдийгээр i> = 0 ба j> = 0:
    1. Хэрэв эхний мөр [i] == хоёр дахь мөр [j] бол:
      1. i-, j-
    2. Бусад
      1. j-
  3. If i > = 0:
    1. буцах хуурамч
  4. буцах үнэн

Is Subsequence Leetcode шийдлийн хэрэгжилт

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;
}

Java програм

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

Is Дараагийн Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (мин (M, N)) хүртэл давталт хийсээр байна i эсвэл j тэг болно. M ба N нь утаснуудын урт юм.

Сансрын нарийн төвөгтэй байдал

O (1) санах ойд тогтмол орон зайг ашигладаг тул.