首页  »   数据结构与算法

给一个字符串集合,判断这个集合的元素是否可以串连,该怎么处理

网友分享于:2013-02-15  浏览:5次
给一个字符串集合,判断这个集合的元素是否可以串连
每个字符串都是两个拉拉伯数字组成,00~99

串连的规则,前一个字符串的尾部和后一个字符串的开头相同,即可串连

比如集合为如下几个字符串

01 12 23 34 45

这个集合可串连,串连的结果为 012345

但这个集合是最理想的情况,实际情况是所有元素是无序的,可串连的两个元素并不保证相邻,也并不保证先后顺序与串连结果一致,而且串连结果也可能并不唯一。

比如
22 22 22 21 12
可以串连成 222212、222122、221222等

如何快速的判断出是否可串连,并列出所有的串连方式呢


我想到的方法只是每种排列方式都去判断一下,但这样效率太低,如果一个集合的元素个数为n,那就是判断n!次

------解决方案--------------------
分别计算0-9这10个数字出现在第一位和第二位的次数 用来判断是否有可行的解。
只有次数完全相等 或者有两个数字分别差了1的时候 才有可行解。
------解决方案--------------------
可以转为汉米尔顿回路问题NP的。

相关解决方案

最新解决方案