ನಂತರದ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ  


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಫೇಸ್ಬುಕ್ ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ pinterest ಯಾಂಡೆಕ್ಸ್
ಅಲ್ಗಾರಿದಮ್ಗಳು ಕೋಡಿಂಗ್ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ದುರಾಸೆ ಸಂದರ್ಶನ ಸಂದರ್ಶನ ಪೂರ್ವಭಾವಿ ಲೀಟ್‌ಕೋಡ್ LeetCodeSolutions ಸ್ಟ್ರಿಂಗ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ  

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ ಎರಡು ವಿಭಿನ್ನ ನೀಡಲಾಗಿದೆ ತಂತಿಗಳು. ಮೊದಲ ಸ್ಟ್ರಿಂಗ್ ಎ ಎಂದು ಕಂಡುಹಿಡಿಯುವುದು ಗುರಿಯಾಗಿದೆ ನಂತರದ ಎರಡನೆಯದರಲ್ಲಿ.

ಉದಾಹರಣೆಗಳು

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

ನಂತರದ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಪಿನ್

ಅಪ್ರೋಚ್ (ಪುನರಾವರ್ತಿತ)  

ನಾವು ಅವುಗಳ ತುದಿಗಳಿಂದ ತಂತಿಗಳನ್ನು ಹೊಂದಿಸಲು ಪ್ರಾರಂಭಿಸಬಹುದು ಎಂದು ನೋಡುವುದು ಸುಲಭ. ತಂತಿಗಳ ಕೊನೆಯ ಅಕ್ಷರಗಳು ಹೊಂದಿಕೆಯಾದರೆ, ಮೂಲದಿಂದ ಪಡೆಯಬಹುದಾದ ಎರಡು ತಂತಿಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವಲ್ಲಿ ನಮಗೆ ಕಡಿಮೆ ಉಪ-ಸಮಸ್ಯೆ ಇದೆ ನಂತರ ಅವರ ಕೊನೆಯ ಅಕ್ಷರಗಳನ್ನು ಬಿಡುವುದು ನಂತರದ ಮಾನದಂಡಗಳನ್ನು ಅನುಸರಿಸುತ್ತದೆ. ಅಂತಿಮ ಅಕ್ಷರಗಳು ಹೊಂದಿಕೆಯಾಗದಿದ್ದರೆ, ಅದರಲ್ಲಿ ಮುಂದೆ ಹುಡುಕಲು ನಾವು ಎರಡನೇ ಸ್ಟ್ರಿಂಗ್‌ನ ಕೊನೆಯ ಅಕ್ಷರವನ್ನು ಮಾತ್ರ ಬಿಡುತ್ತೇವೆ.

ಪ್ರತಿ ಪುನರಾವರ್ತಿತ ಕರೆಯಲ್ಲಿ ಅಕ್ಷರಗಳನ್ನು ಹೋಲಿಸಲು ತಂತಿಗಳ ಸೂಚ್ಯಂಕಗಳನ್ನು ನಿಯತಾಂಕಗಳಾಗಿ ರವಾನಿಸುವ ಮೂಲಕ ಇದನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಮಾಡಬಹುದು.

ಕ್ರಮಾವಳಿ

  1. ಸೂಚ್ಯಂಕ ಮೊದಲ ಸ್ಟ್ರಿಂಗ್‌ನ ಕೊನೆಯ ಸೂಚಿಯನ್ನು ಸೂಚಿಸುತ್ತದೆ ಮತ್ತುಪುನರಾವರ್ತಿತ ಕರೆಗಳಲ್ಲಿ ಎರಡನೇ ಸ್ಟ್ರಿಂಗ್‌ನ ಕೊನೆಯ ಸೂಚಿಯನ್ನು ಸೂಚಿಸುತ್ತದೆ
  2. If i == -1:
    1. ನಾವು ಮೊದಲ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ಹಾದುಹೋಗಿದ್ದೇವೆ, ಹಿಂತಿರುಗಿ ನಿಜವಾದ
  3. If j == -1:
    1. ನಾವು ಮೊದಲ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ಹಾದುಹೋಗಿದ್ದೇವೆ, ಹಿಂತಿರುಗಿ ಸುಳ್ಳು
  4. If ಮೊದಲ_ ಸ್ಟ್ರಿಂಗ್ [i] == ಎರಡನೇ_ ಸ್ಟ್ರಿಂಗ್ [ಜೆ]:
    1. ಸೂಚ್ಯಂಕಗಳೊಂದಿಗೆ ಪುನರಾವರ್ತಿತ ಕಾರ್ಯಗಳನ್ನು ಕರೆ ಮಾಡಿ (i - 1, j - 1)
  5. ಸೂಚ್ಯಂಕಗಳೊಂದಿಗೆ ಪುನರಾವರ್ತಿತ ಕ್ರಿಯೆಯ ಫಲಿತಾಂಶವನ್ನು ಹಿಂತಿರುಗಿ (i, j - 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 ತಂತಿಗಳ ಉದ್ದಗಳು.

ಸಹ ನೋಡಿ
ಎನ್-ನೇ ಟ್ರಿಬೊನಾಕಿ ಸಂಖ್ಯೆ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ನಿಮಿಷ (ಎಂ, ಎನ್) ಪುನರಾವರ್ತಿತ ಕರೆಗಳಿಂದಾಗಿ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ.

ಅಪ್ರೋಚ್ (ಎರಡು-ಪಾಯಿಂಟರ್ಸ್)  

ನಾವು ಮೇಲಿನ ತಂತ್ರವನ್ನು ಎರಡು ಪಾಯಿಂಟರ್‌ಗಳನ್ನು ನಿರ್ವಹಿಸುವ ಮೂಲಕ ಪುನರಾವರ್ತಿಸಬಹುದು 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

ಸಂಕೀರ್ಣತೆಯ ವಿಶ್ಲೇಷಣೆ ಈಸ್ ನಂತರದ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ನಿಮಿಷ (ಎಂ, ಎನ್)) ನಾವು ಪುನರಾವರ್ತಿಸುವವರೆಗೂ i ಅಥವಾ ಜೆ ಶೂನ್ಯವಾಗುತ್ತದೆ. M ಮತ್ತು N ತಂತಿಗಳ ಉದ್ದಗಳು.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1) ನಾವು ಮೆಮೊರಿಯಲ್ಲಿ ಸ್ಥಿರ ಜಾಗವನ್ನು ಬಳಸುತ್ತಿದ್ದಂತೆ.

1