З'яўляецца наступным рашэннем Leetcode


Узровень складанасці Лёгка
Часта пытаюцца ў Саман амазонка Bloomberg facebook Google Microsoft Pinterest Яндэкс
Дынамічнае праграмаванне Прагны Радок

Пастаноўка праблемы

У гэтай праблеме нам дадзены два розныя радкі. Мэта складаецца ў тым, каб даведацца, ці з'яўляецца першы радок а паслядоўнасць другога.

Прыкладаў

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

З'яўляецца наступным рашэннем Leetcode

Падыход (рэкурсіўны)

Гэта лёгка зразумець, што мы можам пачаць супастаўляць радкі з іх канцоў. Калі сімвалы ў апошняй з радкоў супадаюць, мы маем паменшаную падзадачу знайсці, ці можна знайсці дзве радкі з арыгінальных пасля скідаючы іх апошнія сімвалы, прытрымлівайцеся крытэрыяў наступнасці. Калі канцавыя сімвалы не супадаюць, мы скідаем толькі апошні сімвал другой радкі, каб шукаць у ёй наперад.

Гэта можна зрабіць рэкурсіўна, перадаючы індэксы радкоў у якасці параметраў для параўнання знакаў пры кожным рэкурсіўным выкліку.

Алгарытм

  1. індэкс пазначае апошні індэкс першага радка іабазначае апошні індэкс другога радка ў рэкурсіўных выкліках
  2. If я == -1:
    1. Мы цалкам прайшлі першы радок, return праўда
  3. If j == -1:
    1. Мы цалкам прайшлі першы радок, return ілжывы
  4. If first_string [i] == second_string [j]:
    1. выклікаць рэкурсіўныя функцыі з індэксамі (i - 1, j - 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

Аналіз складанасці рашэння з наступным штрых-кодам

Складанасць часу

O (мін. (N, M)) бо нам трэба паўтарацца, пакуль не пройдзе любая з радкоў. N і M - гэта даўжыні радкоў.

Касмічная складанасць

O (мін (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. Вяртаць ілжывы
  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

Аналіз складанасці рашэння з наступным штрых-кодам

Складанасць часу

O (мін (M, N)) як мы працягваем паўтараць да я ці j становіцца нулем. M і N - даўжыні струн.

Касмічная складанасць

O (1) паколькі мы выкарыстоўваем пастаянную прастору ў памяці.