从字典条目创建给定的字符串

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)。因此，执行时间就像fibonacci数：t(n) = t(n - 1) + t(n - 2)一样增长。(您可以通过插入计数器来验证它。)因此，复杂性当然不是多项式。(这甚至不是最糟糕的输入)

但是您可以使用追忆轻松地改进您的解决方案。注意，函数words的输出只取决于一件事:我们要在原始字符串中的哪个位置开始。E.，如果我们有一个字符串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;
}

尽管如此，我还是鼓励您将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。

正规情形下HashSet的存在性检验是Theta(1)，而在最坏情况下是O(n)。

所以，算法的正常情况复杂性是Theta(n^2)，最坏的情况- O(n^3)。

编辑：我混淆了递归和迭代的顺序，所以这个答案是错误的。实际上，时间以指数形式依赖于n (例如，与斐波那契数的计算相比)。

更有趣的是如何改进算法的问题。传统上，字符串操作使用后缀树。您可以用字符串构建后缀树，并在algo开始时将所有节点标记为“未跟踪”。然后遍历一组中的字符串，每次使用某个节点时，将其标记为“跟踪”。如果集合中的所有字符串都在树中找到，这将意味着原始字符串包含set中的所有子字符串。如果所有节点都被标记为跟踪，这将意味着，该字符串仅由set中的子字符串组成。

该方法的实际复杂度取决于树构造算法等多种因素，但它至少允许将问题划分为几个独立的子任务，从而通过最昂贵的子任务的复杂性来度量最终的复杂度。