is_subsequence.md

Is Subsequence

Задача с LeetCode.

Условие

Даны две строки s и t, вернуть true, если s является подпоследовательностью t, или false в противном случае.

Подпоследовательность строки — это новая строка, которая образована из исходной строки путем удаления некоторых (может быть ни одного) символов без нарушения относительного положения оставшихся символов. (т. е. «ace» является подпоследовательностью «abcde», а «aec» — нет).

Ограничения:

0 <= s.length <= 100 0 <= t.length <= 104

Строки s и t состоят только из строчных английских букв.

Примеры

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

Решение

В данной задаче главное - это заметить, что как только мы находим элемент из s строки в t строке, то все, что 'левее' найденного элемента (включая его самого) - нас больше не интересует.

Пример:

Example 1:

Input: s = "abc", t = "qweahbgdc"
Output: true

На первой итерации мы ищем 'a' и найдем ее на позиции 3 (нумерация с 0). Вторая итерация будет искать 'b' и начинать поиск следует с позиции 3 + 1 = 4 (На 3-ей у нас 'a'). Третья итерация будет искать 'c' и начинать поиск следует с позиции 6 (На 5-ой у нас 'b')

Это происходит потому, что нам важен порядок расположения найденных элементов из 's' в 't'.

Для этого заведем два счетчика: для обеих строк. Счетчик 'sp' нужен для итерирования по 's'. Счетчик 'tp' нужен для итерирования по 't'.

Счетчик 'sp' увеличивается только тогда, когда мы нашли элемент в 't'. При этом счетчик 'tp' растет всегда - мы итерируемся по строке.

    public static boolean isSubsequence(String s, String t) {
        if (s.length() > t.length()) {
            return false;
        }

        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        int sp = 0;
        int tp = 0;

        while (sp < sarr.length && tp < tarr.length) {
            if (sarr[sp] == tarr[tp]) {
                sp++;
            }

            tp++;
        }

        return sp == sarr.length;
    }