求可通过字符串数组元素拼接出至少两种方式的最短字符串算法问题

给定字符串数组S，允许重复使用S中的元素，通过拼接数组元素构造新字符串，部分字符串可通过多种不同的元素拼接顺序构造得到。

示例 #

S = {a, ab, ba}
则字符串"aba"可通过2种方式构造：

• "a" + "ba"
• "ab" + "a"

问题需求 #

给定字符串数组S，找出可通过至少两种不同拼接方式得到的最短字符串；若不存在符合要求的字符串，输出-1。

你之前采用的生成所有排列拼接后查重的思路存在本质问题：

1. 允许元素重复使用的前提下排列是无限多的，根本无法穷举
2. 即使限制拼接长度，复杂度也会随长度指数级上升，数组规模稍大就完全无法运行

采用广度优先搜索(BFS)结合状态去重的思路，可高效找到最短的歧义拼接字符串：
核心逻辑是按字符串长度从小到大遍历，第一个出现的有两种拼接方式的字符串就是答案，不需要处理更长的结果。

具体实现步骤 #

1. 预处理：先去重S中的重复元素，如果有重复元素直接返回该元素，它本身就是最短答案
2. 状态定义：用哈希表记录每个字符串后缀对应的拼接路径数，只保留长度不超过S中最长元素长度的后缀即可，不需要存完整字符串，大幅降低内存占用
3. BFS初始化：将S中所有元素作为初始状态入队，每个元素的路径计数为1
4. 逐层遍历队列：
   • 取出队头的当前字符串，如果已经有其他路径生成过完全相同的字符串，直接返回该字符串作为答案
   • 遍历S中所有元素，和当前字符串拼接得到新字符串
   • 对新字符串取所有长度不超过S最长元素长度的后缀，如果该后缀没被记录过就入队，记录路径数为1；如果已经被记录过，路径数+1后大于等于2，对应的完整新字符串就是答案
5. 队列遍历完仍无符合要求的结果，返回-1

该算法时间复杂度仅和S的元素数量、S中元素的最大长度相关，不会出现指数级爆炸的问题，可通过所有测试用例。

内容的提问来源于stack exchange，提问作者unglinh279