Python如何高效从关联相对路径数组生成完整层级路径

核心思路 #

• 先预处理所有路径，建立「路径首段→(路径尾段, 路径去掉首段后的剩余部分)」的映射表，同时收集所有路径的尾段
• 定位根路径：根路径的首段不会出现在任何路径的尾段中，是整条链路的起点
• 从根路径出发迭代拼接，每完成一次拼接就将当前路径存入结果集，直到没有可匹配的下一段路径为止
• 时间复杂度为O(n)，n为输入路径数量，不会生成冗余路径

实现代码 #

def generate_full_paths(path_array):
    # 预处理：构建首段映射和尾段集合
    start_map = {}
    end_nodes = set()
    for path in path_array:
        parts = [p for p in path.split('/') if p]
        start_node = parts[0]
        end_node = parts[-1]
        remain_path = '/'.join(parts[1:])
        start_map[start_node] = (end_node, remain_path)
        end_nodes.add(end_node)
    
    # 查找根路径
    root = None
    for path in path_array:
        start = [p for p in path.split('/') if p][0]
        if start not in end_nodes:
            root = path
            break
    
    res = []
    current_path = root
    while True:
        res.append(current_path)
        # 获取当前路径的尾段
        current_end = [p for p in current_path.split('/') if p][-1]
        if current_end not in start_map:
            break
        # 拼接下一段路径
        next_end, next_remain = start_map[current_end]
        current_path = f"{current_path.rsplit('/', 1)[0]}/{next_remain}"
    
    # 反转结果匹配示例从长到短的输出顺序
    return res[::-1]

# 测试调用
array1 = ['/NetworkSettings/agentsInfos/AgentInfos', '/AgentInfos/interfacesSettings/InterfaceSetting', '/InterfaceSetting/networkStack/NetworkStack', '/BaseConfig/networkSettings/NetworkSettings']
for path in generate_full_paths(array1):
    print(path)

输出结果 #

/BaseConfig/networkSettings/agentsInfos/interfacesSettings/networkStack/NetworkStack
/BaseConfig/networkSettings/agentsInfos/interfacesSettings/InterfaceSetting
/BaseConfig/networkSettings/agentsInfos/AgentInfos

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