392. Is Subsequence

Задача

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

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

Примеры

Пример 1

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

Пример 2

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

Решение

Решение

var isSubsequence = function(s, t) {
    if (t.length < s.length) return false;
    if (!s.length) return true;
 
    let targetIndex = 0;
 
    for (let i = 0; i < t.length - (s.length - 1 - targetIndex); i++) {
        if (t[i] === s[targetIndex]) {
            targetIndex++;
        }
 
        if (targetIndex === s.length) {
            return true;
        }
    }
 
    return false;
};

Решение 2 (Two Pointers)

/**
 * Временная сложность: O(T), где T - длина t
 * Пространственная сложность: O(1)
 */
var isSubsequence = function(s, t) {
    let sIdx = 0;
    let tIdx = 0;
 
    while (sIdx < s.length && tIdx < t.length) {
        if (s[sIdx] === t[tIdx]) {
            sIdx++;
        }
        tIdx++;
    }
 
    return sIdx === s.length;
};