परिणाम उपचारात्मक समाधान है


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना ब्लूमबर्ग Facebook गूगल माइक्रोसॉफ्ट Pinterest Yandex
गतिशील प्रोग्रामिंग लालची तार

समस्या का विवरण

इस समस्या में, हमें दो अलग-अलग दिए गए हैं तार। लक्ष्य यह पता लगाना है कि क्या पहला तार एक है परिणाम को दूसरे का।

उदाहरण

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

परिणाम उपचारात्मक समाधान है

दृष्टिकोण (पुनरावर्ती)

यह देखना आसान है कि हम उनके छोर से तारों का मिलान शुरू कर सकते हैं। यदि स्ट्रिंग्स के अंतिम में वर्ण मेल खाते हैं, तो हमें यह पता लगाने की एक उप-समस्या है कि क्या मूल से दो तार प्राप्त किए जा सकते हैं बाद अपने अंतिम पात्रों को छोड़ने के बाद के मानदंड का पालन करें। यदि अंतिम वर्ण मेल नहीं खाते हैं, तो हम इसमें आगे की खोज करने के लिए केवल दूसरे स्ट्रिंग के अंतिम वर्ण को छोड़ते हैं।

यह प्रत्येक पुनरावर्ती कॉल पर वर्णों की तुलना करने के लिए पैरामीटर के रूप में स्ट्रिंग के सूचक को पास करके पुनरावर्ती रूप से किया जा सकता है।

कलन विधि

  1. सूची पहले स्ट्रिंग के अंतिम सूचकांक को दर्शाता है औरपुनरावर्ती कॉल में दूसरे स्ट्रिंग के अंतिम सूचकांक को दर्शाता है
  2. If मैं == -1:
    1. हमने पहले स्ट्रिंग को पूरी तरह से पीछे छोड़ दिया है <strong>उद्देश्य</strong>
  3. If जे == -1:
    1. हमने पहले स्ट्रिंग को पूरी तरह से पीछे छोड़ दिया है असत्य
  4. If first_string [i] == second_string [j]:
    1. सूचकांकों के साथ पुनरावर्ती कार्य कहते हैं (i - 1, j - 1)
  5. सूचकांकों के साथ पुनरावर्ती कार्य का परिणाम लौटाएं (i, j - 1)

के कार्यान्वयन के बाद 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;
}

जावा प्रोग्राम

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

जटिलता परिणाम Leetcode समाधान की जटिलता है

समय जटिलता

O (न्यूनतम (N, M)) जब तक हम तार में से किसी का पता नहीं लगाते हैं तब तक पुनरावृत्ति करने की आवश्यकता होती है। N और M तार की लंबाई हैं।

अंतरिक्ष जटिलता

O (न्यूनतम (M, N) पुनरावर्ती कॉल के कारण सबसे खराब स्थिति में।

दृष्टिकोण (दो-बिंदु)

हम दो बिंदुओं को बनाए रखते हुए, उपरोक्त तकनीक का उपयोग कर सकते हैं i और संबंधित स्ट्रिंग्स के अंतिम सूचकांकों को संग्रहीत करने के लिए। जब तक कि दोनों में से कोई भी शून्य न हो जाए, हम उसमें पुनरावृत्ति कर सकते हैं। अगर i (पहली स्ट्रिंग का सूचक) 0 से अधिक या उसके बराबर है, हम पहले स्ट्रिंग को पूरी तरह से पार करने में सक्षम नहीं हैं, और इसलिए, यह दूसरे के बाद का नहीं है। और, हम सच लौटाते हैं।

कलन विधि

  1. दो पॉइंटर्स इनिशियलाइज़ करें मैं और जे दोनों तारों के अंतिम सूचकांकों को संग्रहीत करना।
  2. जबकि i> = 0 और j> = 0:
    1. यदि पहला_स्ट्रिंग [i] == second_string [j]:
      1. i- j-
    2. अन्य
      1. j-
  3. If i > = 0:
    1. वापसी असत्य
  4. वापसी <strong>उद्देश्य</strong>

के कार्यान्वयन के बाद 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;
}

जावा प्रोग्राम

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

जटिलता परिणाम Leetcode समाधान की जटिलता है

समय जटिलता

O (न्यूनतम (M, N)) जब तक हम इसे जारी रखते हैं मैं या जे शून्य हो जाता है। एम और एन स्ट्रिंग्स की लंबाई हैं।

अंतरिक्ष जटिलता

ओ (1) जैसे हम मेमोरी में निरंतर स्थान का उपयोग करते हैं।