Substring with Concatenation of All Words

Сложная№30фиксированный размер

Дана строка s и список слов одинаковой длины. Найди все индексы в s, с которых подряд стоят все слова, каждое по одному разу, в любом порядке. Наш пример: s = «stobeabeto», words = [«to», «be»] — ответ [6, 1]: «beto» с индекса 6 и «tobe» с индекса 1.

30 Substring with Concatenation of All WordsРазбор · 1×

Пример: s = «stobeabeto», words = [«to», «be»]. Слова текущего прохода подчёркнуты; под s — need, seen и found.

0s1t2o3b4e5a6b7e8t9oneed—seen—found—
ещё не дошлиокновходящее словоуходящее слово, лишнеевышло из окнасобрано из слов

В каждом слове 2 буквы: L = 2

01/75
сначала · назад · пуск · шаг
Скорость
1function findSubstring(s, words):
2 L = len(words[0])
3 n = len(words)
4 need = count of each word in words
5 found = empty list
6 for offset from 0 to L - 1:
7 seen = empty map // missing keys: 0
8 for right from offset to len(s) - L, step L:
9 word = s[right .. right + L - 1]
10 seen[word] = seen[word] + 1
11 start = right - (n - 1) * L
12 if start - L >= offset:
13 old = s[start - L .. start - 1]
14 seen[old] = seen[old] - 1
15 if every w in need has seen[w] == need[w]:
16 add start to found
17 return found
состояние
L
2
n
–
need
–
found
–
offset
–
seen
–
right
–
word
–
start
–
old
–
историянажмите шаг, чтобы вернуться

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

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

  1. Ответ — это n слов подряд, поэтому окно фиксированное, n · L букв, и сдвигается на целое слово: одно слово входит, одно уходит, seen обновляется за O(1).
  2. Сдвиг на слово проходит только начала offset, offset + L, …, поэтому проходы от 0 до L - 1 вместе пробуют каждое начало. Здесь «tobe» с индекса 1 видит только проход от 1.
  3. В окне ровно n слов, поэтому если у каждого слова счётчик как в need, места для чужих не остаётся: окно — это наши слова в каком-то порядке.

Сложность

Время O(|s| · (L + n)): L проходов вместе дают около |s| шагов, и на каждом шаге вырезается слово из L букв и проверяется need, где не больше n слов. Память O(n · L + |s|): need хранит слова, а seen — каждое слово, встреченное за проход, даже ушедшее, со счётчиком 0.

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

Решить на LeetCode ↗

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