算法 - 怎么进行如下的字符串数组排序？

问题描述

问 题

给定字符串数组，要求进行判断是否存在以下序列

前一个字符串末尾字符等于后一个字符串首字符。

例如：

{"ab","de","bc","cd"} # 此字符串数组满足条件

{"ab","bc","cd","fg"} # 此字符串数组不满足条件

解决方案

其实就是七桥问题，把一个字符串视作从首字母到尾字母的有向链接，求特定字符串集合能不能一次不重复走完。从图论的角度来看，由于可能存在不连通的子图，所以不能简单地用各个节点的度来判断，但节点的度可以用来快速排除不符合的集合。

所以很简单，如果集合中存在这样的序列，必然是以下情况之一：

1. 循环。所有节点的出度等于入度；

2. 不循环。除了某两个节点外，其他所有节点的出度等于入度。

如果符合上面的条件，那么还要跑一次 dfs 看能不能单路径遍历所有边。

如果要排序，那就是 dfs 出来的那条路径。

这篇关于算法 - 怎么进行如下的字符串数组排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！