🔍 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. Проходим по каждому паттерну и проверяем вхождение. Если вошло, увеличиваем счётчик.
➡️ Сложность
strings.Contains внутри использует алгоритм поиска подстроки. При длине word = n и pattern = m это O(n·m) в худшем случае. С учётом ограничений задачи в 100 символов это несущественно.
➡️ Решить
Задача дня на 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 символов это несущественно.
➡️ Решить