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


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

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

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

ตัวอย่าง

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 คือความยาวของสตริง

ดูสิ่งนี้ด้วย
โซลูชัน Leetcode หมายเลข N-th Tribonacci

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

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) เมื่อเราใช้พื้นที่คงที่ในหน่วยความจำ

1