Is Subsequence

Лёгкая№392два массива

Даны две строки, короткая и длинная. Нужно понять, можно ли получить короткую из длинной, вычёркивая в длинной буквы и не меняя порядок оставшихся. Наши примеры: «cat» в «chart» — да; «tac» в «chart» — нет.

392 Is SubsequenceРазбор · 1×

Пример: s = «cat», t = «chart». j идёт по t на каждом шаге, i идёт по s, только когда буквы совпали.

st0c1a2ti0c1h2a3r4t
ещё не дошлипод указателемсовпалипропущены в t

i — на первой букве s, «c»: её ищем первой

01/22
сначала · назад · пуск · шаг
Скорость
1function isSubsequence(s, t):
2 i = 0
3 j = 0
4 while i < len(s) and j < len(t):
5 if s[i] == t[j]:
6 i = i + 1
7 j = j + 1
8 return i == len(s)
состояние
i
0
j
–
s[i]
c
t[j]
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Взять первую подходящую букву t никогда не хуже, чем более позднюю: всё, что поместится после поздней, поместится и после ранней — после неё t осталось больше.
  2. Буква t, которая не равна искомой, не пригодится и потом: следующие буквы s должны стоять после текущей, а эта буква — раньше неё.
  3. Если i дошёл до конца s, все буквы нашлись по порядку: да. Если раньше кончилась t, какой-то букве s не нашлось места после предыдущих: нет.

Сложность

Время O(n), где n — длина t: j сдвигается на букву каждый шаг, поэтому цикл идёт не больше n раз. Память O(1): только два индекса.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.