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

Question

在最近的一次工作面试中，我被要求给出以下问题的解决方案:

给定一个字符串 s(没有空格)和一个字典，返回字典中组成该字符串的单词。

例如，s= peachpie, dic= {peach, pie}, result={peach, pie}。

我会问这个问题的决策变体:

if s can be composed of words in the dictionary return yes, otherwise return 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 执行时，都会产生两个递归调用:with 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(这会使它变得更加简单)。

编辑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]);