🔍 LeetCode Daily: считаем подстроки за один проход

Задача дня на LeetCode — Number of Strings That Appear as Substrings in Word. Дан массив строк patterns и строка word. Нужно вернуть количество строк из patterns, которые входят в word как подстроки.

Подстрока — это непрерывная последовательность символов внутри строки. Если patterns = ["a","abc","bc","d"] и word = "abc", ответ будет 3: входят "a", "abc" и "bc", а "d" нет.

➡️ Решение
 
В Go для этого есть готовый инструмент — strings.Contains. Проходим по каждому паттерну и проверяем вхождение. Если вошло, увеличиваем счётчик.

import "strings"
 
func numOfStrings(patterns []string, word string) int {
count := 0
for _, p := range patterns {
if strings.Contains(word, p) {
count++
}
}
return count
}

➡️ Сложность
 
strings.Contains внутри использует алгоритм поиска подстроки. При длине word = n и pattern = m это O(n·m) в худшем случае. С учётом ограничений задачи в 100 символов это несущественно.

➡️ Решить