Создать данную строку из словарных статей

Question

Во время недавнего собеседования меня попросили дать решение следующей проблемы:

Учитывая строку s (без пробелов) и словарь, вернуть слова в словаре, составляющиестрока.

Например, s= peachpie, dic= {peach, pie}, result={peach, pie}.

Я попрошу вариант решения этой проблемы:

, если s может состоять из словв словаре возвращаем yes, в противном случае возвращаем no.

Мое решение для этого было в возврате (написано на Java)

public static boolean words(String s, Set<String> dictionary)
{
    if ("".equals(s))
        return true;

    for (int i=0; i <= s.length(); i++)
    {
        String pre = prefix(s,i); // returns s[0..i-1]
        String suf = suffix(s,i); // returns s[i..s.len]
        if (dictionary.contains(pre) && words(suf, dictionary))
            return true;
    }
    return false;
}

public static void main(String[] args) {
    Set<String> dic = new HashSet<String>();
    dic.add("peach");
    dic.add("pie");
    dic.add("1");

    System.out.println(words("peachpie1", dic)); // true
    System.out.println(words("peachpie2", dic)); // false
}

Какова временная сложностьэто решение?Я вызываю рекурсивно в цикле for, но только для префиксов, которые есть в словаре.

Есть идеи?

Answer 1

Вы можете легко создать случай, когда выполнение программы занимает как минимум экспоненциальное время.Давайте просто возьмем слово aaa...aaab, где a повторяется n раз.Словарь будет содержать только два слова, a и aa.

b. В конце убедитесь, что функция никогда не найдет совпадение и, следовательно, никогда не завершится преждевременно.

На каждом words выполнение, будут созданы два рекурсивных вызова: с suffix(s, 1) и suffix(s, 2).Следовательно, время выполнения увеличивается как числа Фибоначчи: t(n) = t(n - 1) + t(n - 2).(Вы можете проверить это, вставив счетчик.) Таким образом, сложность определенно не является полиномиальной.(и это даже не наихудший вариант)

Но вы можете легко улучшить свое решение с помощью Memoization .Обратите внимание, что вывод функции words зависит только от одного: с какой позиции в исходной строке мы начинаем.То есть, если у нас есть строка abcdefg и вызывается words(5), не имеет значения, как именно составлена ​​abcde (как ab+c+de или a+b+c+d+e или что-то еще).Таким образом, нам не нужно каждый раз пересчитывать words("fg").
В примитивной версии это можно сделать следующим образом

public static boolean words(String s, Set<String> dictionary) {
    if (processed.contains(s)) {
        // we've already processed string 's' with no luck
        return false;
    }

    // your normal computations
    // ...

    // if no match found, add 's' to the list of checked inputs
    processed.add(s);
    return false;
}

PS Тем не менее, я призываю вас изменить words(String)до words(int).Таким образом, вы сможете сохранять результаты в массиве и даже преобразовывать весь алгоритм в DP (что значительно упростит его).

edit 2
Поскольку я неМногое, кроме работы, вот решение DP (динамическое программирование).Та же идея, что и выше.

    String s = "peachpie1";
    int n = s.length();
    boolean[] a = new boolean[n + 1];
    // a[i] tells whether s[i..n-1] can be composed from words in the dictionary
    a[n] = true; // always can compose empty string

    for (int start = n - 1; start >= 0; --start) {
        for (String word : dictionary) {
            if (start + word.length() <= n && a[start + word.length()]) {
                // check if 'word' is a prefix of s[start..n-1]
                String test = s.substring(start, start + word.length());
                if (test.equals(word)) {
                    a[start] = true;
                    break;
                }
            }
        }
    }

    System.out.println(a[0]);

Answer 2

Вот решение для динамического программирования, которое подсчитывает общее количество способов разбить строку на слова.Это решает вашу исходную проблему, поскольку строка разложима, если число разложений положительно.

def count_decompositions(dictionary, word):
    n = len(word)
    results = [1] + [0] * n
    for i in xrange(1, n + 1):
        for j in xrange(i):
            if word[n - i:n - j] in dictionary:
                results[i] += results[j]
    return results[n]

Хранилище O (n) и время выполнения O (n ^ 2).

Answer 3

Цикл на всю строку займет n. Поиск всех суффиксов и префиксов займет n + (n - 1) + (n - 2) + .... + 1 (n для первого вызова words, (n - 1) для второго и т. Д.), Что составляет

n^2 - SUM(1..n) = n^2 - (n^2 + n)/2 = n^2 / 2 - n / 2

, что в теории сложности эквивалентно п ^ 2.

Проверка на существование в HashSet в нормальном случае - это Theta (1), но в худшем случае это O (n).

Итак, нормальный случай сложности вашего алгоритма - тета (n ^ 2), а наихудший случай - O (n ^ 3).

РЕДАКТИРОВАТЬ: Я перепутал порядок рекурсии и итерации, поэтому этот ответ неверен. На самом деле время зависит от n в геометрической прогрессии (например, сравните с вычислением чисел Фибоначчи).

Более интересным является вопрос, как улучшить свой алгоритм. Традиционно для строковых операций используется дерево суффиксов . Вы можете построить суффиксное дерево со своей строкой и пометить все узлы как «неотслеживаемые» в начале алгоритма. Затем просмотрите строки в наборе, и каждый раз, когда используется какой-либо узел, пометьте его как «отслеживаемый». Если все строки в наборе найдены в дереве, это будет означать, что исходная строка содержит всех подстрок из набора. И если все узлы помечены как отслеживаемые, это будет означать, что строка состоит из только подстроки из множества.

Фактическая сложность этого подхода зависит от многих факторов, таких как алгоритм построения дерева, но, по крайней мере, позволяет разделить задачу на несколько независимых подзадач и, таким образом, измерить конечную сложность по сложности самой дорогой подзадачи.