Հաջորդականության Leetcode լուծում է  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon Bloomberg facebook Google Microsoft Pinterest Yandex
ալգորիթմները կոդավորում Դինամիկ ծրագրավորում Ագահ հարցազրույց հարցազրույցի պատրաստում LeetCode LeetCodeSolutions String

Խնդիրի հայտարարություն  

Այս խնդրում մեզ երկու տարբեր են տրված տողերը, Նպատակը պարզելն է ՝ արդյոք առաջին տողը a է հետևանք երկրորդից:

Օրինակներ

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

Հաջորդականության Leetcode լուծում էPin

Մոտեցում (ռեկուրսիվ)  

Դա հեշտ է տեսնել, որ մենք կարող ենք սկսել համապատասխանել տողերը դրանց ծայրերից: Եթե ​​տողերի վերջին նիշերը համընկնում են, ապա մենք ունենք նվազեցված ենթախնդիր `պարզելու, թե արդյոք երկու տողերը, որոնք կարելի է ձեռք բերել բնօրինակներից երբ իրենց վերջին նիշերը գցելը հետևում է հետևյալ չափանիշներին: Եթե ​​վերջնական նիշերը չեն համընկնում, մենք նետում ենք միայն երկրորդ տողի վերջին նիշը ՝ դրա մեջ առաջ որոնելու համար:

Դա կարելի է անել ռեկուրսիվ կերպով ՝ տողերի ինդեքսները որպես պարամետրեր փոխանցելով յուրաքանչյուր ռեկուրսիվ զանգի նիշերը համեմատելու համար:

Ալգորիթմ

  1. ինդեքս նշանակում է առաջին տողի վերջին ցուցիչը ևնշանակում է ռեկուրսիվ զանգերի երկրորդ տողի վերջին ցուցիչը
  2. If ես == -1:
    1. Մենք ամբողջությամբ անցել ենք առաջին լարը, վերադարձիր ճիշտ
  3. If ժ == -1:
    1. Մենք ամբողջությամբ անցել ենք առաջին լարը, վերադարձիր սուտ
  4. If առաջին_լարը [i] == երկրորդ_լարը [j]:
    1. զանգահարել ինդեքսներով ռեկուրսիվ գործառույթներ (i - 1, j - 1)
  5. Վերադարձող ֆունկցիայի արդյունքը հետ բերեք ինդեքսներով (i, j - 1)

Is Subquestence 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 է հետևողականության լետոկոդային լուծույթի բարդության վերլուծություն

Timeամանակի բարդություն

O (րոպե (N, M)) քանի որ մենք պետք է կրկնենք այնքան ժամանակ, քանի դեռ լարերից որևէ մեկը չի անցել: N և M լարերի երկարություններն են:

Տես նաեւ,
N- րդ տրիբոնաչիի համարի կոդերի լուծում

Տիեզերական բարդություն

O (րոպե (M, N) ամենավատ դեպքում `ռեկուրսիվ զանգերի պատճառով:

Մոտեցում (երկկետանոց)  

Մենք կարող ենք օգտագործել վերոնշյալ տեխնիկան, կրկնօրինակում ՝ պահպանելով երկու ցուցիչ i և պահպանել համապատասխան տողերի վերջին ցուցանիշները: Մենք կարող ենք կրկնել այնքան ժամանակ, քանի դեռ նրանցից ոչ մեկը չի զրոյի: Եթե i (առաջին տողի ցուցիչը) մեծ է կամ հավասար է 0-ի, մենք չկարողացանք առաջին լարն ամբողջությամբ անցնել, և, հետևաբար, դա երկրորդի հետևանք չէ: Ուրիշ, մենք ճշմարիտ ենք վերադառնում:

Ալգորիթմ

  1. Նախաձեռնեք երկու ցուցիչ ես և ժ երկու լարերի վերջին ցուցանիշների պահպանում:
  2. Ժամանակ i> = 0 և j> = 0:
    1. Եթե ​​first_string [i] == second_string [j]:
      1. i-, j-
    2. Ուրիշ
      1. j-
  3. If i > = 0:
    1. Վերադառնալ սուտ
  4. Վերադառնալ ճիշտ

Is Subquestence 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 է հետևողականության լետոկոդային լուծույթի բարդության վերլուծություն

Timeամանակի բարդություն

O (րոպե (M, N)) քանի որ մենք շարունակում ենք կրկնել մինչև i կամ j դառնում է զրո: M- ը և N- ը լարերի երկարություններն են:

Տիեզերական բարդություն

Ո (1) քանի որ մենք հիշողության մեջ օգտագործում ենք անընդհատ տարածություն:

1