[Python] Algorithm to recursively search a dictionary or list and return the path of each...

I keep almost solving this.

I've got a data set of python dictionaries that contain both lists and dictionaries that also contain lists and dictionaries.

I want to find all instances of a substring in any of the values and I want to know the path I took to find it. I'll make a simplified example:

[
{
"name": "doug",
"foods": [ "cheese", "apple", "hotdog" ],
"address" : { "street": "1st", "house": "12345" },
},
{
"name": "alice",
"foods": ["carrot", "hamburger", "cookie"],
"address": { "street": "iceberg", "house": "5432" },
}
]


If I search for 'do' I want something like

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


The actual data structure doesn't matter. It could be a single long string for all I care. I just need to be able to know that the first entity (doug) had 2 matches for the substring 'do' and one was in his name and one was in his foods list.

And, my actual data is a fair bit more complicated. I'd like my algorithm to work on any arbitrarily nested lists & objects.

Here's my most recent attempt:

def recursive_search(space, hint):
if isinstance(space, int):
# I treat ints as str for matching purposes
space = str(space)
if isinstance(space, str):
# I've reached the end of the path
if hint in space:
# I found one!
return [ space ]
return None
if isinstance(space, list):
list_results = []
for index, item in enumerate(space):
result = recursive_search(item, hint )
if result is None:
continue
result.append(index)
list_results.append(result)
if len(list_results) > 0:
return list_results
return None
if isinstance(space, dict):
dict_results = []
for key, value in space.items():
result = recursive_search(value, hint )
if result is None:
continue
result.append(key)
dict_results.append(result)
if len(dict_results) > 0:
return dict_results
return None
return None


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

This feels like a textbook problem with an elegant answer and that's what I hope for.

Continue reading...