LeetCode 392: решение для JavaScript

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

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

Прежде чем углубляться в решение, давайте на минутку поймем, что такое подпоследовательность.

Подпоследовательность — это последовательность, которая может быть получена из другой последовательности путем удаления некоторых элементов без изменения порядка остальных элементов. Например, {A, B, D} является подпоследовательностью последовательности {A, B, C, D, E}, полученной после удаления {C} и {E}.

Люди часто путают подмассив/подстроку и подпоследовательность. Подмассив или подстрока всегда будут непрерывными, но подпоследовательность не обязательно должна быть непрерывной. То есть подпоследовательности не обязаны занимать последовательные позиции в исходных последовательностях. Но мы можем сказать, что и смежные подпоследовательности, и подмассивы одинаковы.

Другими словами, подпоследовательность является обобщением подстроки или подстрока является уточнением подпоследовательности. Например, {A, C, E} — это подпоследовательность {A, B, C, D, E}, но не подстрока, а {A, B, C} — это и подмассив, и подпоследовательность.

Подход: два указателя

  1. Базовый случай 1.Если длина строки S больше, чем T, вернуть False.
  2. Базовый вариант 2.Если строка S пуста, возвращается значение True.
  3. Объявите две новые переменные iи j и инициализируйте их значением 0.
  4. сравнить символы в их текущих позициях i и j. Если они равны, мы перемещаем оба указателя на следующую позицию в соответствующих строках.
  5. Если они не равны, мы только перемещаем указатель j на следующую позицию в T.
  6. Мы повторяем этот процесс, пока не достигнем конца S или T.
// ES6 Arrow Function
const isSubsequence = (s, t) => {
    // base case
    if(s.length > t.length) return false;
    if(!s) return true;

    let i = 0, j = 0;

    while(i < s.length && j < t.length) {
        if(s[i] == t[j]) {
            i++;
            j++;
        } else {
            j++;
        }
    }

    return i === s.length;
}

Временная сложность:O(N)

Пространственная сложность:O(1)

Подход 2: двухточечный указатель с небольшой модификацией

// ES6 Arrow Function
const isSubsequence = (s, t) => {
    // base case
    if(s.length > t.length) return false;
    if(!s) return true;

    let i = 0; 
    for(let j = 0; j < t.length; j++) {
        if(s[i] == t[j]) i++;
    }

    return i === s.length;
}

Примечание.Время и Пространство Сложность остается прежней.

Я надеюсь, что эта статья предоставила вам ценную информацию и помогла вам лучше понять различные подходы к решению этой проблемы. Удачного кодирования!

Проблема - Leetcode 392

Ссылка на определение подпоследовательности — TechieDelight