139. Word Break

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        HashSet<string> words = new HashSet<string>(wordDict);
        Queue<int> queue = new Queue<int>();
        bool[] seen = new bool[s.Length + 1];
        queue.Enqueue(0);
        while (queue.Count != 0) {
            int start = queue.Dequeue();
            if (start == s.Length) {
                return true;
            }
            for (int end = start + 1; end <= s.Length; end++) {
                if (seen[end]) {
                    continue;
                }
                if (words.Contains(s.Substring(start, end - start))) {
                    queue.Enqueue(end);
                    seen[end] = true;
                }
            }
        }
        return false;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool WordBreak(string s, vector<string> wordDict) {
        HashSet<string> words = new HashSet<string>(wordDict);
        queue<int> queue = new queue<int>();
        bool[] seen = new bool[s.size() + 1];
        queue.Enqueue(0);
        while (queue.size() != 0) {
            int start = queue.Dequeue();
            if (start == s.size()) {
                return true;
            }
            for (int end = start + 1; end <= s.size(); end++) {
                if (seen[end]) {
                    continue;
                }
                if (words.Contains(s.Substring(start, end - start))) {
                    queue.Enqueue(end);
                    seen[end] = true;
                }
            }
        }
        return false;
    }
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        Queue<Integer> queue = new LinkedList<>();
        boolean[] seen = new boolean[s.length() + 1];
        queue.add(0);

        while (!queue.isEmpty()) {
            int start = queue.remove();
            if (start == s.length()) {
                return true;
            }

            for (int end = start + 1; end <= s.length(); end++) {
                if (seen[end]) {
                    continue;
                }

                if (words.contains(s.substring(start, end))) {
                    queue.add(end);
                    seen[end] = true;
                }
            }
        }

        return false;
    }
}

var wordBreak = function (s, wordDict) {
    let words = new Set(wordDict);
    let queue = [0];
    let seen = new Set();
    while (queue.length != 0) {
        let start = queue.shift();
        if (start == s.length) return true;
        for (let end = start + 1; end <= s.length; end++) {
            if (seen.has(end)) continue;
            if (words.has(s.substring(start, end))) {
                queue.push(end);
                seen.add(end);
            }
        }
    }
    return false;
};

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        words = set(wordDict)
        queue = deque([0])
        seen = set()

        while queue:
            start = queue.popleft()
            if start == len(s):
                return True

            for end in range(start + 1, len(s) + 1):
                if end in seen:
                    continue

                if s[start:end] in words:
                    queue.append(end)
                    seen.add(end)

        return 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
}

Algorithm

1️⃣

Инициализация структур данных:

Преобразуйте wordDict в множество words для быстрой проверки вхождения.

Инициализируйте очередь queue начальным значением 0 (индекс начала строки) и множество seen для отслеживания посещённых индексов.

2️⃣

Обход в ширину (BFS):

Пока очередь не пуста, извлекайте первый element из очереди, обозначающий начальную позицию start.

Если start равен длине строки s, возвращайте true, так как достигнут конец строки, и строку можно разделить на слова из словаря.

Итерируйте end от start + 1 до s.length включительно. Для каждого end, проверьте, посещён ли он уже.

3️⃣

Проверка подстроки и обновление структур:

Проверьте подстроку начиная с start и заканчивая перед end. Если substring находится в множестве words, добавьте end в очередь и отметьте его в seen как посещённый.

Если BFS завершается и конечный узел не достигнут, возвращайте false.

😎