c++ - 字符串补全和匹配算法

Question

你有两组：现在S1={B,C,D,T,M,...}，S2={with each other letter of alphabet not present in S1}. 我有一些用 S1(ie. BBWRD)中的辅音构成的字符串，我想根据提供的字典将其转换为单词/句子算法可以用 S2 中的任意数量的字母(ie. dict from spelling mechanism). 填充每个字母之间的空格。'base word'不能更改顺序，不能使用 S1 中的字母/辅音。

我唯一想到的是正则表达式的使用。你能提出任何其他更好的方法吗？或者至少给这种算法命名，这样我就可以进一步搜索。

Answer 1

我会考虑创建一个搜索树。每个节点都会有|S1|子节点，叶子会包含一个可能的单词列表，这些单词可以由给定的首字母缩写词构成（例如 - 例如D路径上的=W->R->D将包含“Word”。在这样的树中搜索会非常快，尽管它将需要存储大量内存以便快速访问。