识别给定字符串列表排序规律 推荐对应实现算法

先对照输入输出做特征映射就能找到核心规则：

• 目标排序结果：['A','C','AC','B','AB','F','D','DF','ADF']
• 把所有字符串反转后得到序列：['A','C','CA','B','BA','F','D','FD','FDA']
  这个反转序列完全符合前缀Trie（字典树）的先根遍历输出逻辑：

1. 每个字符串对应Trie上的一个终止节点
2. 遍历规则为：访问到终止节点时立刻输出对应原字符串，再按预设的同级节点优先级遍历所有子节点
3. 同级节点优先级可按业务需求自定义，本例中根节点的单字符优先级为A > C > B > F > D，非根节点的子节点唯一，不需要额外排序

对应的未反转原字符串的硬约束非常明确：如果字符串X是字符串Y的最长真后缀，X必须排在Y前面，所有约束完全匹配目标结果：

• C是AC的最长真后缀，C排在AC前
• B是AB的最长真后缀，B排在AB前
• D是DF的最长真后缀，D排在DF前
• DF是ADF的最长真后缀，DF排在ADF前
• 无有效最长真后缀的单字符按自定义优先级排序，自然满足在对应长串之前的要求。

这类带前后缀依赖、支持自定义同级元素优先级的排序问题，有两种工业界常用的成熟算法：

方案1：Trie树构建+定制先根遍历（优先选，性能最优） #

这是字符串/序列类前后缀依赖排序的最优方案，时间复杂度O(N*L)，N是待排序元素总数，L是元素平均长度，实现步骤：

1. 预处理：如果是后缀依赖规则（和本例一致，长串的后缀对应短串），先把所有待排序字符串反转；如果是前缀依赖规则，直接用原字符串即可。
2. 构建Trie树：
   • 每个Trie节点存三个属性：子节点映射表（key为字符，value为子节点引用）、是否为终止节点的标记、终止节点对应的原字符串。
   • 逐个遍历预处理后的字符串，逐字符插入Trie，字符串遍历完成后标记当前节点为终止节点，存入原字符串。
3. 先根遍历Trie：
   • 从根节点出发，访问到节点时如果是终止节点，就把对应原字符串加入结果列表。
   • 取出当前节点的所有子节点，按自定义规则排序（比如本例根节点子节点按A、C、B、F、D排序，业务上可以替换为任意规则：出现频率、自定义权重、自然字母序都可以）。
   • 按排序后的顺序递归遍历每个子节点。
4. 遍历完成后得到的结果就是符合要求的排序序列。

对应本例的Python实现参考：

class TrieNode:
    __slots__ = ['children', 'is_end', 'origin_str']
    def __init__(self):
        self.children = dict()
        self.is_end = False
        self.origin_str = ""

def custom_sort(str_list, root_level_priority=None):
    # 初始化Trie根节点
    root = TrieNode()
    for s in str_list:
        # 本例为后缀依赖，反转字符串
        reversed_s = s[::-1]
        cur_node = root
        for c in reversed_s:
            if c not in cur_node.children:
                cur_node.children[c] = TrieNode()
            cur_node = cur_node.children[c]
        cur_node.is_end = True
        cur_node.origin_str = s
    
    res = []
    def dfs(node):
        if node.is_end:
            res.append(node.origin_str)
        # 处理子节点排序
        child_chars = list(node.children.keys())
        if node is root and root_level_priority is not None:
            # 根节点层按自定义优先级排序
            child_chars.sort(key=lambda x: root_level_priority.index(x))
        # 非根节点如果存在多个子节点，可在此处扩展自定义排序规则
        for c in child_chars:
            dfs(node.children[c])
    
    dfs(root)
    return res

# 测试用例
my_list = ['A','AC','F','AB','ADF','D','DF','C','B']
# 本例根节点层（单字符）自定义优先级
priority = ['A','C','B','F','D']
print(custom_sort(my_list, priority))
# 输出：['A', 'C', 'AC', 'B', 'AB', 'F', 'D', 'DF', 'ADF']，和目标完全一致

方案2：拓扑排序 #

如果你的排序依赖不局限于前后缀关系，存在任意的「X必须排在Y前」的偏序约束，就可以用拓扑排序实现，时间复杂度O(N+E)，E是依赖边的总数，实现步骤：

1. 遍历所有元素，统计每个元素的入度，构建邻接表：每存在一条「X必须在Y前」的约束，就添加一条X指向Y的边，Y的入度加1。
2. 初始化队列，把所有入度为0的节点加入队列，加入时按自定义优先级排序，保证同级节点输出顺序符合预期。
3. 依次弹出队首元素加入结果列表，遍历该元素的所有邻接节点，将邻接节点的入度减1，如果邻接节点入度变为0，就按优先级插入队列的对应位置。
4. 所有节点处理完成后就得到排序结果，如果结果长度小于待排元素总数，说明存在循环依赖，无法完成排序。

拓扑排序的优势是灵活度高，支持任意偏序约束，但在纯前后缀依赖的场景下，需要手动配对所有元素的依赖关系，实现比Trie方案繁琐，性能也更低。

• 排序规则基于前缀/后缀包含关系的，优先选Trie+先根遍历方案，性能高、实现简洁，调整同级优先级非常方便。
• 排序依赖是零散的自定义偏序规则，没有统一的前后缀规律的，选拓扑排序方案。

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