Permutation in String

Средняя№567фиксированный размер

Даны две строки, s1 и s2. Нужно понять, есть ли в s2 кусок подряд идущих букв, который состоит из букв s1 в каком-то порядке. Наш пример: s1 = «loot», s2 = «tollotool» — да: «loto» с индекса 3.

567 Permutation in StringРазбор · 1×

Пример: s1 = «loot», s2 = «tollotool». Под s2 — need: сколько каких букв окну ещё не хватает. 0 — бледный, меньше 0 — лишняя буква.

0t1o2l3l4o5t6o7o8lneed—s1 = "loot"
ещё не дошли, не хватаетокновходящая буквауходящая буква, лишняявышло из окна, счётчик 0перестановка s1

В s1 4 буквы: окно длиной 4

01/34
сначала · назад · пуск · шаг
Скорость
1function checkInclusion(s1, s2):
2 m = len(s1)
3 need = count of each letter in s1 // missing keys: 0
4 for right from 0 to len(s2) - 1:
5 need[s2[right]] = need[s2[right]] - 1
6 if right >= m:
7 need[s2[right - m]] = need[s2[right - m]] + 1
8 if every count in need is 0:
9 return true
10 return false
состояние
m
4
need
–
right
–
историянажмите шаг, чтобы вернуться

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

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

  1. Перестановка s1 той же длины, что и s1, поэтому подходят только окна этой длины, а окно сдвигается на одну букву и проходит все места, где она могла бы начаться.
  2. need начинается со счётчиков s1; вошедшая буква отнимает единицу, ушедшая возвращает. Все счётчики равны 0 ровно тогда, когда в окне те же буквы, что в s1, и столько же раз каждая.
  3. Мало, чтобы буквы были те же: в «toll» есть l, o и t, но одна «l» лишняя и одной «o» не хватает. Поэтому словарь хранит счётчики, а не множество.

Сложность

Время O(26 · n), где n — длина s2: каждая буква один раз входит и один раз выходит, а проверка need смотрит не больше 26 счётчиков. Память O(1): не больше 26 счётчиков.

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

Решить на LeetCode ↗

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