સબસેક્વેન્સ લીટકોડ સોલ્યુશન છે


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન બ્લૂમબર્ગ ફેસબુક Google માઈક્રોસોફ્ટ Pinterest યાન્ડેક્ષ
ડાયનેમિક પ્રોગ્રામિંગ લોભી શબ્દમાળા

સમસ્યા નિવેદન

આ સમસ્યામાં, અમને બે અલગ અલગ આપવામાં આવે છે શબ્દમાળાઓ. લક્ષ્ય એ શોધવાનું છે કે પ્રથમ શબ્દમાળા એ અનુગામી બીજા.

ઉદાહરણો

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

સબસેક્વેન્સ લીટકોડ સોલ્યુશન છે

અભિગમ (પુનરાવર્તિત)

આ જોવા માટે સરળ છે કે આપણે તેમના અંતથી શબ્દમાળાઓ મેચ કરવાનું શરૂ કરી શકીએ છીએ. જો શબ્દમાળાઓના અંતમાંના અક્ષરો મેળ ખાય છે, તો પછી અમને તે શોધવા માટેની ઓછી તકલીફ છે કે જે બે શબ્દમાળાઓ મૂળમાંથી મેળવી શકાય છે કે કેમ પછી તેમના છેલ્લા પાત્રો છોડી દેવા અનુગામી માપદંડને અનુસરે છે. જો અંતનાં પાત્રો મેળ ખાતા નથી, તો અમે તેમાં આગળ શોધવા માટે ફક્ત બીજા શબ્દમાળાના છેલ્લા પાત્રને છોડી દઈએ છીએ.

દરેક રિકર્સીવ ક atલમાં અક્ષરોની તુલના કરવા માટે પરિમાણો તરીકે શબ્દમાળાઓના સૂચકાંકો પસાર કરીને આને પુનરાવર્તિત કરી શકાય છે.

અલ્ગોરિધમ

  1. ઇન્ડેક્સ પ્રથમ શબ્દમાળાના છેલ્લા અનુક્રમણિકાને સૂચવે છે અનેપુનરાવર્તિત ક .લ્સમાં બીજા શબ્દમાળાના છેલ્લા અનુક્રમણિકાને સૂચવે છે
  2. If i == -1:
    1. અમે પહેલા શબ્દમાળાને સંપૂર્ણ રીતે પાછળ વળી ગયા છીએ સાચું
  3. If j == -1:
    1. અમે પહેલા શબ્દમાળાને સંપૂર્ણ રીતે પાછળ વળી ગયા છીએ ખોટા
  4. If પ્રથમ_તમારા [i] == સેકન્ડ_સ્ટ્રિંગ [જે]:
    1. સૂચકાંકો સાથે પુનરાવર્તિત કાર્યો ક callલ કરો (હું - 1, જ - 1)
  5. સૂચકાંકો સાથે રિકરિવ ફંક્શનનું પરિણામ પાછા ફરો (હું, જ - 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 શબ્દમાળાઓની લંબાઈ છે.

અવકાશ જટિલતા

ઓ (મિનિટ (એમ, એન) રિકરિવ ક callsલ્સને કારણે સૌથી ખરાબ કિસ્સામાં.

અભિગમ (બે-પોઇંટર્સ)

આપણે ઉપરોક્ત તકનીકનો ઉપયોગ બે પોઇંટરો જાળવી રાખીએ i અને સંબંધિત શબ્દમાળાઓના છેલ્લા સૂચકાંકો સંગ્રહિત કરવા. જ્યાં સુધી તેમાંથી કોઈ એક પણ શૂન્ય ન થાય ત્યાં સુધી આપણે પુનરાવર્તન કરી શકીએ છીએ. જો i (પ્રથમ શબ્દમાળાના નિર્દેશક) 0 કરતા વધારે અથવા બરાબર છે, આપણે પ્રથમ શબ્દમાળાને સંપૂર્ણપણે પસાર કરી શક્યા નથી, અને તેથી, તે બીજાનો અનુગામી નથી. બાકી, આપણે ખરા.

અલ્ગોરિધમ

  1. બે પોઇંટર્સ પ્રારંભ કરો હું અને જે બંને શબ્દમાળાઓના છેલ્લા સૂચકાંકો સંગ્રહિત કરી રહ્યા છીએ.
  2. જ્યારે i> = 0 અને j> = 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

જટિલતા વિશ્લેષણ ઇઝ સબસેક્વેન્સ લીટકોડ સોલ્યુશન

સમય જટિલતા

ઓ (મિનિટ (એમ, એન)) આપણે ત્યાં સુધી પુનરાવર્તન કરીએ છીએ હું અથવા જે શૂન્ય બને છે. એમ અને એન એ શબ્દમાળાઓની લંબાઈ છે.

અવકાશ જટિલતા

ઓ (1) આપણે મેમરીમાં સતત જગ્યા વાપરીશું.