Библиотека Go-разработчика | Golang: “🔍 LeetCode Daily: считаем подстроки за один проход Задача дня на Leet…”

🔍 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 символов это несущественно.

➡️ Решить

📍 Навигация: Вакансии • Задачи • Собесы

🐸 Библиотека Go-разработчика

#ReadySetGo