เป็นโซลูชัน Leetcode ที่ตามมา


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี อเมซอน บลูมเบิร์ก Facebook Google ไมโครซอฟท์ Pinterest Yandex
การเขียนโปรแกรมแบบไดนามิก โลภ เชือก

คำชี้แจงปัญหา

ในปัญหานี้เราได้รับสองอย่างที่แตกต่างกัน เงื่อนไข. เป้าหมายคือการค้นหาว่าสตริงแรกเป็นไฟล์ ต่อมา ของที่สอง

ตัวอย่าง

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

เป็นโซลูชัน Leetcode ที่ตามมา

แนวทาง (เรียกซ้ำ)

นี่เป็นเรื่องง่ายที่จะเห็นว่าเราสามารถเริ่มจับคู่สตริงจากปลายสายได้ หากอักขระสุดท้ายของสตริงตรงกันแสดงว่าเรามีปัญหาย่อยที่ลดลงในการค้นหาว่าสตริงทั้งสองที่สามารถหาได้จากสตริงดั้งเดิมหรือไม่ หลังจาก การทิ้งอักขระสุดท้ายเป็นไปตามเกณฑ์ลำดับต่อมา หากอักขระปิดท้ายไม่ตรงกันเราจะปล่อยเฉพาะอักขระสุดท้ายของสตริงที่สองเพื่อค้นหาข้างหน้า

สิ่งนี้สามารถทำได้แบบวนซ้ำโดยส่งดัชนีของสตริงเป็นพารามิเตอร์เพื่อเปรียบเทียบอักขระในการเรียกซ้ำทุกครั้ง

ขั้นตอนวิธี

  1. ดัชนี หมายถึงดัชนีสุดท้ายของสตริงแรกและหมายถึงดัชนีสุดท้ายของสตริงที่สองในการเรียกซ้ำ
  2. If ผม == -1:
    1. เราได้ย้อนกลับสตริงแรกอย่างสมบูรณ์แล้วย้อนกลับ จริง
  3. If เจ == -1:
    1. เราได้ย้อนกลับสตริงแรกอย่างสมบูรณ์แล้วย้อนกลับ เท็จ
  4. If first_string [i] == second_string [j]:
    1. เรียกใช้ฟังก์ชันแบบเรียกซ้ำพร้อมดัชนี (ผม - 1, j - 1)
  5. ส่งคืนผลลัพธ์ของฟังก์ชันเรียกซ้ำพร้อมดัชนี (ผมเจ - 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;
}

โปรแกรม 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

การวิเคราะห์ความซับซ้อนของโซลูชัน Leetcode ที่ตามมา

ความซับซ้อนของเวลา

O (นาที (N, M)) ในขณะที่เราต้องทำซ้ำจนกว่าจะข้ามสตริงอย่างใดอย่างหนึ่ง N และ M คือความยาวของสตริง

ความซับซ้อนของอวกาศ

O (นาที (M, N) ในกรณีที่เลวร้ายที่สุดเนื่องจากการโทรซ้ำ

แนวทาง (สองตัวชี้)

เราสามารถใช้เทคนิคข้างต้นซ้ำได้โดยรักษาตัวชี้สองตัว i และ เพื่อจัดเก็บดัชนีสุดท้ายของสตริงที่เกี่ยวข้อง เราสามารถวนซ้ำจนกว่าทั้งสองอย่างจะกลายเป็นศูนย์ ถ้า i (ตัวชี้ของสตริงแรก) มีค่ามากกว่าหรือเท่ากับ 0 เราไม่สามารถสำรวจสตริงแรกได้อย่างสมบูรณ์และด้วยเหตุนี้จึงไม่ใช่ลำดับที่สอง ที่อื่นเรากลับจริง

ขั้นตอนวิธี

  1. เริ่มต้นตัวชี้สองตัว ฉันและเจ จัดเก็บดัชนีสุดท้ายของทั้งสองสตริง
  2. ในขณะที่ ฉัน> = 0 และ j> = 0:
    1. ถ้า first_string [i] == second_string [j]:
      1. i-, j-
    2. อื่น
      1. j-
  3. If i > = 0:
    1. กล้บ เท็จ
  4. กล้บ จริง

การนำโซลูชัน 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

การวิเคราะห์ความซับซ้อนของโซลูชัน Leetcode ที่ตามมา

ความซับซ้อนของเวลา

O (นาที (M, N)) ในขณะที่เราทำซ้ำไปเรื่อย ๆ จนถึง ฉันหรือญ กลายเป็นศูนย์ M และ N คือความยาวของสตริง

ความซับซ้อนของอวกาศ

O (1) เมื่อเราใช้พื้นที่คงที่ในหน่วยความจำ