特殊交错串编码

Question

交织规则是由字母的方式将一个字到另一个，在信中，像下面展示，形成了一个新词：

a p p l e 
o l d 
    = 
aoplpdle 

不要紧，哪个字先行。 （oalpdple也是有效的）

问题给出了一个字符串{old，apple，talk，aoplpdle，otladlk}的向量，找到所有有效的从向量中交叉两个单词的单词。

最简单的解决方案要求至少O（n^2）的时间复杂度，每隔两个字取一个交织字，检查它是否在向量中。

有没有更好的解决方案？

Answer 1

按长度排序。您只需检查2个条目（单词...）的长度总和等于现有条目长度的组合。

这会降低您的平均复杂度。我没有花时间来计算最糟糕的复杂度，但它也可能低于O（n^2）。

您还可以通过尽早拒绝匹配来优化“内部循环” - 您并不需要构造整个交错字以拒绝匹配 - 将候选字与2个输入字一起迭代，直到找到不匹配为止。这不会降低您最糟糕的复杂度，但会对整体性能产生积极影响。