Сложность: 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 {
let words = Set(wordDict)
var queue = [0]
var seen = Set<Int>()
while !queue.isEmpty {
let start = queue.removeFirst()
if start == s.count {
return true
}
for end in (start + 1)...s.count {
if seen.contains(end) {
continue
}
let startIndex = s.index(s.startIndex, offsetBy: start)
let endIndex = s.index(s.startIndex, offsetBy: end)
let substring = String(s[startIndex..<endIndex])
if words.contains(substring) {
queue.append(end)
seen.insert(end)
}
}
}
return false
}Ставь 👍 и забирай 📚 Базу знаний