ແມ່ນວິທີແກ້ໄຂ Leetcode  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon Bloomberg ເຟສບຸກ ກູໂກ Microsoft Pinterest Yandex
ຂັ້ນຕອນວິທີ ລະຫັດ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ຄວາມໂລບມາກ ການສໍາພາດ ການສໍາພາດກ່ອນ LeetCode LeetCodeSolutions string

ຖະແຫຼງການບັນຫາ  

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບສອງຢ່າງທີ່ແຕກຕ່າງກັນ strings. ເປົ້າ ໝາຍ ແມ່ນເພື່ອຄົ້ນຫາວ່າສາຍ ທຳ ອິດແມ່ນ a ຕໍ່ມາ ຂອງສອງ.

ຕົວຢ່າງ

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

ແມ່ນວິທີແກ້ໄຂ Leetcode

ວິທີການ (Recursive)  

ນີ້ງ່າຍທີ່ຈະເຫັນວ່າພວກເຮົາສາມາດເລີ່ມຕົ້ນຈັບຄູ່ກັບສາຍຈາກປາຍຂອງພວກເຂົາ. ຖ້າຕົວອັກສອນຢູ່ແຖວສຸດທ້າຍຂອງສາຍກົງກັນ, ຫຼັງຈາກນັ້ນພວກເຮົາມີບັນຫາຍ່ອຍທີ່ນ້ອຍລົງໃນການຊອກຫາວ່າສອງເຊືອກທີ່ສາມາດໄດ້ມາຈາກສາຍເດີມ ຫຼັງຈາກ ການຫຼຸດລົງຕົວອັກສອນສຸດທ້າຍຂອງເຂົາເຈົ້າປະຕິບັດຕາມມາດຖານຕໍ່ມາ. ຖ້າຕົວອັກສອນສຸດທ້າຍບໍ່ກົງກັນ, ພວກເຮົາພຽງແຕ່ວາງຕົວອັກສອນສຸດທ້າຍຂອງສາຍທີສອງເພື່ອຄົ້ນຫາຢູ່ຂ້າງ ໜ້າ.

ສິ່ງນີ້ສາມາດເຮັດໄດ້ໂດຍການຜ່ານຕົວຊີ້ວັດຂອງເຊືອກເປັນຕົວກໍານົດການປຽບທຽບຕົວລະຄອນໃນທຸກໆການເອີ້ນທີ່ເອີ້ນຄືນ.

ລະບົບວິເຄາະ

  1. ດັດຊະນີ ສະແດງດັດຊະນີສຸດທ້າຍຂອງສາຍ ທຳ ອິດແລະໝາຍ ເຖິງດັດສະນີສຸດທ້າຍຂອງສາຍທີສອງໃນການຮຽກຮ້ອງໂທຫາ
  2. If i == -1:
    1. ພວກເຮົາໄດ້ຂ້າມສາຍ ທຳ ອິດຢ່າງສົມບູນ, ກັບຄືນມາ ທີ່ແທ້ຈິງ
  3. If j == .1:
    1. ພວກເຮົາໄດ້ຂ້າມສາຍ ທຳ ອິດຢ່າງສົມບູນ, ກັບຄືນມາ ທີ່ບໍ່ຖືກຕ້ອງ
  4. If first_string [i] == ວິນາທີທີສອງ [j]:
    1. ໂທຫາ ໜ້າ ທີ່ເອີ້ນຕົວແທນດ້ວຍຕົວຊີ້ວັດ (i - 1, ຈ - 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;
}

ໂຄງການ 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 (min (N, M)) ດັ່ງທີ່ພວກເຮົາ ຈຳ ເປັນຕ້ອງໄດ້ຕໍ່ຄືນຈົນກ່ວາທັງສອງຂອງສາຍເຊືອກຖືກຜ່ານໄປ. N ແລະ M ແມ່ນຄວາມຍາວຂອງຊ່ອຍແນ່.

ເບິ່ງ
ການແກ້ໄຂ Leetcode ເລກ N-th Tribonacci

ຄວາມສັບສົນໃນອະວະກາດ

O (min (M, N) ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດຍ້ອນການຮຽກຮ້ອງການໂທຫາ.

ວິທີການ (ສອງຈຸດ)  

ພວກເຮົາສາມາດ ນຳ ໃຊ້ເຕັກນິກຂ້າງເທິງນີ້, ເລິ່ມຕົ້ນໂດຍການຮັກສາສອງຈຸດ i ແລະ ເພື່ອເກັບຮັກສາຕົວຊີ້ວັດສຸດທ້າຍຂອງຊ່ອຍແນ່. ພວກເຮົາສາມາດແກ້ແຄ້ນຈົນກວ່າມັນຈະກາຍເປັນສູນ. ຖ້າ i (ຕົວຊີ້ຂອງສາຍ ທຳ ອິດ) ໃຫຍ່ກວ່າຫລືເທົ່າກັບ 0, ພວກເຮົາບໍ່ສາມາດຂ້າມສາຍ ທຳ ອິດຄົບຖ້ວນໄດ້, ແລະດ້ວຍເຫດນີ້, ມັນບໍ່ແມ່ນການຕິດຕໍ່ຂອງທີສອງ. ອື່ນ, ພວກເຮົາກັບຄືນມາເປັນຄວາມຈິງ.

ລະບົບວິເຄາະ

  1. ເລີ່ມຕົ້ນສອງຈຸດ i ແລະ j ການເກັບຮັກສາສາຍສະແດງສຸດທ້າຍຂອງທັງສອງສາຍ.
  2. ໃນຂະນະທີ່ i> = 0 ແລະ j> = 0:
    1. ຖ້າຫາກວ່າ first_string [i] == second_string [j]:
      1. i-, j-
    2. ອື່ນ ໆ
      1. j-
  3. If i > = 0:
    1. Return ທີ່ບໍ່ຖືກຕ້ອງ
  4. Return ທີ່ແທ້ຈິງ

ການປະຕິບັດແມ່ນວິທີແກ້ໄຂ 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 (min (M, N)) ດັ່ງທີ່ພວກເຮົາຮັກສາ iterating ຈົນກ່ວາ i ຫຼື j ກາຍເປັນສູນ. M ແລະ N ແມ່ນລວງຍາວຂອງສາຍ.

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ຄົງທີ່ໃນຄວາມຊົງ ຈຳ.

ເບິ່ງ
ແຖວ K Weakest ຢູ່ໃນ Matrix Leetcode Solution