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

Question

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

6

在最近的一次面试中，我被要求提出以下问题的解决方案：给定一个字符串 s（不含空格）和一个字典，返回由字典组成该字符串的单词。例如，s=peachpie，dic={peach，pie}，结果为{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循环中进行递归调用，但只针对字典中存在的前缀。

有什么想法吗？

- Itsik

1

这个词必须只由字典中的单词组成吗？例如，如果“apple”不在字典中，那么“applepie”的结果会是什么？ - Gumbo

@Gumbo，applepie的结果显然是错误的。看一下问题的定义：如果s可以由字典中的单词组成，则返回yes。apple不在字典中。 - Itsik

这只能用于由一个或两个单词组成的字符串，如果是“tastyapplepie”和{'tasty'，'apple'，'pie'}，它将无法正常工作。 - Matt Phillips

1

@Matt，它能够工作是因为我在后缀上递归调用了“words”。 - Itsik

@j 不好意思，你的例子的答案是错误的。 - Itsik

显示剩余3条评论

3个回答

1

这是一个动态规划的解决方案，它计算将字符串分解为单词的总方法数。它解决了您的原始问题，因为如果分解的数量为正，则字符串是可分解的。

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)。

- user97370

正如我写给Nikita的那样，我喜欢动态编程方法，它更快。但我提出这个问题是因为我在分析自己的算法时遇到了困难。 - Itsik

@Paul：你能解释一下这个算法是如何工作的，或者至少“results”的内容是什么吗？我很难理解它的目的是什么，以及它如何计算分解的数量。 - divegeek

1

@divegeek：我来试一下。results[i]是使用字典单词分解字符串的最后i个字符的方法数。我们从字符串末尾向前工作，始终利用我们已经计算过的后缀分解计数。如果results[i]只存储1表示“最后i个字符至少有1种分解可能”，否则为0，那么内部的if语句会更容易理解，实际上写成if word[n-i:n-j] in dictionary and results[j] == 1 then results[i] = 1。 - j_random_hacker

@divegeek：在我提出的简化算法中，外部循环按递增长度顺序遍历每个后缀。内部（j）循环本质上是在询问：“是否存在任何更短的可分解后缀（长度为j），可以用来得到一个长度为i的可分解后缀？”（请记住j<i）。事实上，不仅可以计算出这是否可能，而且可以计算出不同分解的数量，这只是一些花哨的展示罢了 :) - j_random_hacker

@j_random_hacker：你可以通过在代码中将 += 改为 |= 来实现更简单的版本。 - user97370

显示剩余2条评论

0

遍历整个字符串的循环将需要 n。查找所有后缀和前缀将需要 n + (n - 1) + (n - 2) + .... + 1（第一次调用 words 需要 n，第二次需要 (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呈指数关系（例如，计算斐波那契数列）。

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

这种方法的实际复杂性取决于许多因素，如树构建算法，但至少它允许将问题分成几个独立的子任务，因此可以通过最昂贵的子任务的复杂度来衡量最终复杂度。

- ffriend

“O(n^3)” 这个算法还不错：你得等上一分钟才能得到“n=40”的答案 :) - Nikita Rybak

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nikita Rybak · Accepted Answer

您可以轻松创建一个程序，其中执行至少需要指数时间。我们只需要取一个单词 aaa...aaab，其中 a 重复出现了 n 次。这个字典只包含两个单词： a 和 aa。

结尾的b 确保该函数永远不会找到匹配项，因此永远不会过早退出。

在每个 words 的执行中，将产生两个递归调用：使用 suffix(s, 1) 和 suffix(s, 2)。因此，执行时间增长如斐波那契数列: t(n) = t(n - 1) + t(n - 2)。（您可以通过插入计数器进行验证。）所以，复杂性显然不是多项式的。（而且这甚至不是最坏的输入情况）

但是，您可以轻松地通过记忆化技术来改进解决方案。请注意，函数 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;
}

我建议你将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]);