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

Question

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

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

例如：

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

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

Answer 1

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

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

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

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

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

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

Answer 2

将字符串用spilt方法将空格分开，然后遍历，判断第一个字符串的尾部是否和第二个开头一样，依次类推

Answer 3

ted 大的算法非常完整，就算法的部份可以參考他的說法，以下是我用 Python 實現的一個範例(algo.py):

首先是一個基礎的 dfs function，不需要做任何事前確認就能夠正確地辨識出 string list 是否符合條件:

def dfs(prestr, str_lst):
    for idx, string in enumerate(str_lst):
        if not prestr or string[0] == prestr[-1]:
            if len(str_lst)==1:
                return [string]
            # print(string, str_lst[:idx] + str_lst[idx+1:])  # 反註解掉此行用以觀察搜尋的過程
            result = dfs(string, str_lst[:idx] + str_lst[idx+1:])
            if result:
                return [string] + result
    return None

但是有了事前檢查可以減少不必要的 dfs。

用來作提前檢查的 pre_check:

import collections

def pre_check(str_lst):

    heads = (string[0] for string in str_lst)
    tails = (string[-1] for string in str_lst)
    first_head = None
    last_tail = None

    head_counter = collections.Counter(heads)
    tail_counter = collections.Counter(tails)

    sub_counter = head_counter-tail_counter
    if len(sub_counter) > 1:
        return False, None, None
    elif len(sub_counter)==1:
        first_head = list(sub_counter)

    sub_counter = tail_counter-head_counter
    if len(sub_counter) > 1:
        return False
    elif len(sub_counter)==1:
        last_tail = list(sub_counter)

    return True, first_head, last_tail

有作 pre_check 的 完整版 check:

def check(str_lst):
    result, first_head, last_tail = pre_check(str_lst)
    if result:
        if (first_head is None and last_tail is None) or (first_head and last_tail):
            return dfs(None, str_lst)
        else:
            return None
    else:
        return None

測試結果:

>>> from algo import dfs, check
>>> s1 = ["ab", "de", "bc", "cd"]
>>> dfs(None, s1)
['ab', 'bc', 'cd', 'de']
>>> check(s1)
['ab', 'bc', 'cd', 'de']
>>> s2 = ["ab","bc","cd","fg"]
>>> dfs(None, s2)  # 回傳 None 代表 s2 並不符合條件
>>> check(s2)  # 回傳 None 代表 s2 並不符合條件
>>> s3 = ["gh","ab","ef","hi","bc","cd","fg","de"]  # 無循環
>>> dfs(None, s3)
['ab', 'bc', 'cd', 'de', 'ef', 'fg', 'gh', 'hi']
>>> check(s3)
['ab', 'bc', 'cd', 'de', 'ef', 'fg', 'gh', 'hi']
>>> s4 = ["gh","ab","ef","ha","bc","cd","fg","de"]  # 循環
>>> dfs(None, s4)
['gh', 'ha', 'ab', 'bc', 'cd', 'de', 'ef', 'fg']
>>> check(s4)
['gh', 'ha', 'ab', 'bc', 'cd', 'de', 'ef', 'fg']