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

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
}

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

Любые идеи?

Answer 1

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

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

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

Но вы можете легко улучшить свое решение с помощью Записка. Анкет Заметьте, этот выход функции words Зависит только от одной вещи: в какой позиции в оригинальной строке мы начинаем. EE, если у нас есть строка 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 (что сделает его намного проще).

Редактировать 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

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

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

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

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

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

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