algorithm - 如何检查是否可以在字典中找到所有子字符串

Question

我有一个问题想尽可能高效地解决。举个例子，我得到一串单词:A B C D 并且我有一个包含 5 个条目的“字典”:

A
B C
B D
D
E

字典告诉我输入字符串中可以包含哪些子字符串。我想尽可能高效地检查是否可以将整个输入字符串拆分为子字符串，以便在字典中找到所有子字符串。

在示例中，可以通过将输入字符串拆分为 A、B C 和 D 来找到输入字符串

我想知道是否有比暴力破解所有可能的子字符串更好的方法。我检查子字符串是否在字典中的次数越少越好。

如果没有可能的解决方案，则无需知道找不到哪些子串。

谢谢。

Answer 1

我会使用树而不是字典。这将提高搜索速度并消除用于搜索的子树。