特殊交錯串編碼

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個輸入字一起迭代，直到找到不匹配爲止。這不會降低您最糟糕的複雜度，但會對整體性能產生積極影響。