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.Если длина строки S больше, чем T, вернуть False.
- Базовый вариант 2.Если строка S пуста, возвращается значение True.
- Объявите две новые переменные iи j и инициализируйте их значением 0.
- сравнить символы в их текущих позициях i и j. Если они равны, мы перемещаем оба указателя на следующую позицию в соответствующих строках.
- Если они не равны, мы только перемещаем указатель j на следующую позицию в T.
- Мы повторяем этот процесс, пока не достигнем конца 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