Είναι η συνέχεια Leetcode Solution  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις πλίθα αμαζόνα Bloomberg Facebook Google Microsoft Pinterest Yandex
αλγόριθμοι κωδικοποίησης Δυναμικός προγραμματισμός Άπληστος συνέντευξη συνέντευξηprep LeetCode LeetCodeSolutions κορδόνι

Δήλωση προβλήματος  

Σε αυτό το πρόβλημα, μας δίνουν δύο διαφορετικά χορδές. Ο στόχος είναι να μάθετε αν η πρώτη συμβολοσειρά είναι α ακολουθία του δεύτερου.

Παραδείγματα

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

Είναι η συνέχεια Leetcode SolutionΚαρφώστε

Προσέγγιση (Αναδρομική)  

Είναι εύκολο να καταλάβουμε ότι μπορούμε να αρχίσουμε να ταιριάζουμε τις χορδές από τα άκρα τους. Εάν οι χαρακτήρες στο τελευταίο των συμβολοσειρών ταιριάζουν, τότε έχουμε ένα μειωμένο υπο-πρόβλημα να βρούμε αν οι δύο χορδές μπορούν να ληφθούν από τις αρχικές μετά αφήνοντας τους τελευταίους χαρακτήρες τους ακολουθήστε τα κριτήρια ακολουθίας. Εάν οι τελικοί χαρακτήρες δεν ταιριάζουν, ρίχνουμε μόνο τον τελευταίο χαρακτήρα της δεύτερης συμβολοσειράς για αναζήτηση μπροστά του.

Αυτό μπορεί να γίνει αναδρομικά περνώντας τους δείκτες των συμβολοσειρών ως παραμέτρους για να συγκρίνετε τους χαρακτήρες σε κάθε αναδρομική κλήση.

Αλγόριθμος

  1. Περιεχόμενα δηλώνει τον τελευταίο δείκτη της πρώτης συμβολοσειράς καιδηλώνει το τελευταίο ευρετήριο της δεύτερης συμβολοσειράς σε αναδρομικές κλήσεις
  2. If i == -1:
    1. Έχουμε περάσει εντελώς την πρώτη συμβολοσειρά, επιστροφή αληθής
  3. If j == -1:
    1. Έχουμε περάσει εντελώς την πρώτη συμβολοσειρά, επιστροφή ψευδής
  4. If first_string [i] == second_string [j]:
    1. καλέστε αναδρομικές συναρτήσεις με δείκτες (i - 1, j - 1)
  5. Επιστρέψτε το αποτέλεσμα της αναδρομικής λειτουργίας με δείκτες (i, j - 1)

Εφαρμογή της λύσης Le Subcode ακολουθίας είναι

Πρόγραμμα 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

Ανάλυση πολυπλοκότητας της λύσης Le Subcode ακολουθίας είναι

Χρόνος πολυπλοκότητας

O (ελάχ. (N, M)) καθώς πρέπει να επαναληφθούμε μέχρι να διασχίσει οποιαδήποτε από τις χορδές. N M είναι τα μήκη των χορδών.

Βλέπε επίσης
Λύση Leetcode N-th Tribonacci

Διαστημική πολυπλοκότητα

O (ελάχ. (M, N) στη χειρότερη περίπτωση λόγω αναδρομικών κλήσεων.

Προσέγγιση (Two-Pointers)  

Μπορούμε να χρησιμοποιήσουμε την παραπάνω τεχνική, επαναληπτικά διατηρώντας δύο δείκτες i για να αποθηκεύσετε τους τελευταίους δείκτες των αντίστοιχων συμβολοσειρών. Μπορούμε να επαναλάβουμε έως ότου ένα από τα δύο γίνει μηδέν. Αν i (δείκτης της πρώτης συμβολοσειράς) είναι μεγαλύτερος από ή ίσος με 0, δεν μπορέσαμε να διασχίσουμε την πρώτη συμβολοσειρά εντελώς, και ως εκ τούτου, δεν πρόκειται για δεύτερη. Αλλιώς, επιστρέφουμε αλήθεια.

Αλγόριθμος

  1. Αρχικοποιήστε δύο δείκτες εγώ και j αποθηκεύοντας τους τελευταίους δείκτες και των δύο χορδών.
  2. Ενώ i> = 0 και j> = 0:
    1. Αν το first_string [i] == second_string [j]:
      1. i-, j-
    2. Αλλού
      1. j-
  3. If i > = 0:
    1. απόδοση ψευδής
  4. απόδοση αληθής

Εφαρμογή της λύσης Le Subcode ακολουθίας είναι

Πρόγραμμα 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

Ανάλυση πολυπλοκότητας της λύσης Le Subcode ακολουθίας είναι

Χρόνος πολυπλοκότητας

O (ελάχ. (M, N)) καθώς συνεχίζουμε να επαναλαμβάνουμε μέχρι εγώ ή j γίνεται μηδέν. Τα Μ και Ν είναι τα μήκη των χορδών.

Διαστημική πολυπλοκότητα

Ο (1) καθώς χρησιμοποιούμε σταθερό χώρο στη μνήμη.

1