Задача: 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.

😎 Решение:

function wordBreak($s, $wordDict) {
    $words = array_flip($wordDict); // Use an associative array to simulate a set for quick lookup
    $queue = [0];
    $seen = [];

    while (!empty($queue)) {
        $start = array_shift($queue); // Dequeue the first element
        if ($start == strlen($s)) {
            return true;
        }
        for ($end = $start + 1; $end <= strlen($s); $end++) {
            if (isset($seen[$end])) {
                continue;
            }
            $substring = substr($s, $start, $end - $start);
            if (isset($words[$substring])) {
                array_push($queue, $end); // Enqueue
                $seen[$end] = true; // Mark this end index as seen
            }
        }
    }
    return false;
}

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