Golang | LeetCode

Задача: 139. Word Break Сложность: medium Дана строка s и словарь строк wordDict. Верните true, если строку s можно разделить на последовательность одного или нескольких слов из словаря, разделённых пробелами. Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении. Пример:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

👨‍💻 Алгоритм: 1⃣Инициализация структур данных: Преобразуйте wordDict в множество words для быстрой проверки вхождения. Инициализируйте очередь queue начальным значением 0 (индекс начала строки) и множество seen для отслеживания посещённых индексов. 2⃣Обход в ширину (BFS): Пока очередь не пуста, извлекайте первый элемент из очереди, обозначающий начальную позицию start. Если start равен длине строки s, возвращайте true, так как достигнут конец строки, и строку можно разделить на слова из словаря. Итерируйте end от start + 1 до s.length включительно. Для каждого end, проверьте, посещён ли он уже. 3⃣Проверка подстроки и обновление структур: Проверьте подстроку начиная с start и заканчивая перед end. Если подстрока находится в множестве words, добавьте end в очередь и отметьте его в seen как посещённый. Если BFS завершается и конечный узел не достигнут, возвращайте false. 😎 Решение:

func wordBreak(s string, wordDict []string) bool {
    words := make(map[string]bool)
    queue := make([]int, 0)
    seen := make([]bool, len(s)+1)
    for _, word := range wordDict {
        words[word] = true
    }
    queue = append(queue, 0)
    for len(queue) > 0 {
        start := queue[0]
        queue = queue[1:]
        if start == len(s) {
            return true
        }
        for end := start + 1; end <= len(s); end++ {
            if seen[end] {
                continue
            }
            if _, ok := words[s[start:end]]; ok {
                queue = append(queue, end)
                seen[end] = true
            }
        }
    }
    return false
}

Ставь 👍 и забирай 📚 Базу знаний