Є наступним рішенням Leetcode


Рівень складності Легко
Часто запитують у саман Амазонка Bloomberg Facebook Google Microsoft Пінтерест Яндекс
Динамічне програмування Жадібний рядок

Постановка проблеми

У цій задачі нам дано два різних струни. Мета - з’ясувати, чи є перший рядок символом послідовність другого.

прикладів

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

Є наступним рішенням Leetcode

Підхід (рекурсивний)

Це легко зрозуміти, що ми можемо розпочати збіг рядків з їх кінців. Якщо символи в останній з рядків збігаються, то ми маємо зменшену підзадачу на пошук того, чи можуть бути отримані два рядки з вихідних після скидаючи останні символи, дотримуйтесь критеріїв подальшої послідовності. Якщо кінцеві символи не збігаються, ми лише скидаємо останній символ другого рядка для пошуку в ньому вперед.

Це можна зробити рекурсивно, передаючи індекси рядків як параметри для порівняння символів при кожному рекурсивному виклику.

Алгоритм

  1. індекс позначає останній індекс першого рядка тапозначає останній індекс другого рядка в рекурсивних викликах
  2. If i == -1:
    1. Ми повністю пройшли перший рядок, return правда
  3. If j == -1:
    1. Ми повністю пройшли перший рядок, return false
  4. If first_string [i] == second_string [j]:
    1. викликати рекурсивні функції з індексами (i - 1, j - 1)
  5. Повертає результат рекурсивної функції з індексами (i, j - 1)

Реалізація рішення підконтрольного Leetcode

Програма С ++

#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. Повертати false
  4. Повертати правда

Реалізація рішення підконтрольного Leetcode

Програма С ++

#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)) оскільки ми продовжуємо ітерацію до i або j стає нулем. M і N - довжини струн.

Складність простору

O (1) оскільки ми використовуємо постійний простір у пам'яті.