实现递归搜索嵌套字典/列表并返回匹配元素路径的算法

问题分析 #

你需要处理任意嵌套的Python字典/列表数据，找出所有包含指定子串的值，并返回从根节点到该值的完整路径（格式如[[0,"name","doug"],[0,"foods","2","hotdog"]]）。但你当前的递归函数返回的是嵌套混乱的结构[[['doug', 'name'], [['hotdog', 2], 'foods'], 0]]，不符合预期。

原代码的核心问题：

• 路径顺序颠倒：找到匹配值后从底层往上层append索引/键，导致路径是[值, 键, 索引]的倒序
• 结果嵌套层级错误：每次递归返回的结果被直接嵌套，最终形成多层嵌套的列表，而非每个路径独立成一个子列表

优雅解决方案 #

我们可以通过传递当前路径的可变列表，在递归过程中动态维护路径，找到匹配时将完整路径复制后加入结果列表。这种方式逻辑清晰，避免嵌套混乱，且能处理任意深度的嵌套结构。

优化后的代码 #

def search_nested(space, hint):
    results = []
    
    def _recursive_search(current, hint, current_path):
        # 处理整数转字符串的情况
        if isinstance(current, int):
            current_str = str(current)
            if hint in current_str:
                # 找到匹配，复制当前路径并添加当前值，加入结果
                results.append(current_path + [current_str])
            return
        
        # 处理字符串匹配
        if isinstance(current, str):
            if hint in current:
                results.append(current_path + [current])
            return
        
        # 处理列表：遍历索引和元素
        if isinstance(current, list):
            for idx, item in enumerate(current):
                # 将当前索引转为字符串（匹配示例格式），加入路径
                _recursive_search(item, hint, current_path + [str(idx)])
            return
        
        # 处理字典：遍历键和值
        if isinstance(current, dict):
            for key, value in current.items():
                _recursive_search(value, hint, current_path + [key])
            return
        
        # 其他类型忽略
        return
    
    _recursive_search(space, hint, [])
    return results

代码说明 #

1. 结果列表维护：使用外部函数的results列表收集所有匹配路径，避免递归返回值的嵌套问题
2. 路径传递：递归时通过current_path + [新节点]的方式生成新路径（避免修改原路径），保证每个递归分支的路径独立
3. 类型处理：
   • 整数转为字符串后检查子串匹配，匹配时将字符串形式的整数加入路径
   • 字符串直接检查子串匹配
   • 列表遍历索引，将索引转为字符串（匹配示例中的"2"格式）后加入路径；若需要整数索引，去掉str(idx)转换即可
   • 字典遍历键，直接将键加入路径
4. 路径格式：最终路径从根节点到匹配值依次排列，完全符合你期望的格式

测试示例 #

假设测试数据如下：

test_data = [
    {
        "name": "doug",
        "foods": ["pizza", "burger", "hotdog"]
    }
]

调用search_nested(test_data, "do")会返回：

[['0', 'name', 'doug'], ['0', 'foods', '2', 'hotdog']]

和你期望的格式一致。

原代码的问题修正点 #

• 原代码在找到匹配后返回[space]，然后往上递归时append索引/键，导致路径倒序且嵌套层级混乱
• 优化后的代码通过正向构建路径，每次递归传递新路径，找到匹配时直接将完整路径加入结果，彻底解决了嵌套和倒序问题

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