Задача.
Дана строка s и набор заданных слов wordDict. Нужно проверить можно ли полностью разделить исходную строку на отдельные слова из заданного словаря.
Например,
s = "leetcode", wordDict = ["leet","code"] -> true
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] -> false.
Ссылка на leetcode: https://leetcode.com/problems/word-break/description/
Решение.
Для решения будем использовать динамическое программирование (dynamic programming). А точнее его top-down версию.
Решение top-down методом состоит из 4 этапов:
1) Составляем рекурсивное выражение, которое связывает решение для задачи через подзадачи используя ветвления в задаче.
2) Определяем базовые кейсы, т.е. кейсы когды мы знаем ответ на задачу и можем прервать погружение в рекурсию
3) Пишем код решения
4) Добавляем кэш (memoization), для того чтобы не решать одни и те же подзадачи много раз, а просто вернуть результат из кэша.
Рекурсивное выражение.
Допустим у нас есть строка leetcode. Мы можем просто перебирать варианты, куда поставить первый разделитель. После первой буквы: l eetcode. Потом после второй буквы: le etcode. И т.д.
На каждом шаге будем проверять, содержится ли подстрока слева от разделителя в словаре или нет. Если нет, то перейдем к следующему варианту. Если да, то рекурсивно вызываем нашу функцию от правой части строки. Т.е. в данном случае мы поставим разделитель после leet и рекурсивно вызываем функцию от code. Для code все аналогично. Вначале попробуем поставить разделитель после первой буквы: c ode, потом после второй и т.д.
Базой кейс.
Если в какой-то момент мы вызвали нашу рекурсивную функцию от пустой строки, это значит, что мы смогли до этого поставить уже все разделители и рекурсивно вызвали от пустой строки. Для примера с leetcode. Мы поставили разделитель после leet, потом после code и вызвали рекурсивно от правой части, что является пустой строкой. В таком случае наша функцию должна вернуть true. Т.к. мы смогли разбить строку на слова из словаря.
Пишем код.
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// Помещаем слова в set для быстрой (O(1)) проверки
//наличия слова в словаре.
Set<String> dict = new HashSet<>(wordDict);
return helper(s, 0, dict);
}
//В качестве параметра будем передавать индекс начала строки
//для которой мы решаем задачу. Т.е. начало правой подстроки
//после предыдущего разбиения.
private boolean helper(String s, int start, Set<String> dict) {
//Базовый случай. Когда мы разбили всю строку
//на слова из словаря - вернуть true.
if (start == s.length()) {
return true;
}
//Перебираем разбиения
for (int i = start; i < s.length(); i++) {
String candidate = s.substring(start, i + 1);
//Если строка содержится в словаре, то разбиваем
//строку тут и делаем рекурсивный вызов для правой части.
if (dict.contains(candidate)) {
boolean result = helper(s, i + 1, dict);
//Если такое разбиение сработало, то возвращаем true,
//если нет - то продолжаем перебор.
if (result) {
return true;
}
}
}
//Если не одно из разбиений не сработало, то возвращаем false.
return false;
}
}
Добавляем кэш (memoization)
Наша функция helper может быть вызвана для одного и того же значения start множество раз. Чтобы не производит вычисления для одних и тех же значений start мы просто закэшируем результат и вернем значение из кэша.
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
//Кэш
Map<Integer, Boolean> cache = new HashMap<>();
return helper(s, 0, dict, cache);
}
private boolean helper(String s, int start, Set<String> dict, Map<Integer, Boolean> cache) {
if (start == s.length()) {
return true;
}
//Если значение есть в кэше, то возвращаем результат
//из кэша и не производим вычисления.
if (cache.containsKey(start)) {
return cache.get(start);
}
boolean result = false;
for (int i = start; i < s.length(); i++) {
String candidate = s.substring(start, i + 1);
if (dict.contains(candidate)) {
result = helper(s, i + 1, dict, cache);
if (result) {
break;
}
}
}
//Сохраняем результат вычисления в кэше
cache.put(start, result);
return result;
}
}
Top comments (0)