DEV Community

faangmaster
faangmaster

Posted on

Задача на динамическое программирование. Разделение на слова.

Задача.

Дана строка 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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Добавляем кэш (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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)