Algorithmus zum rekursiven Durchsuchen eines Wörterbuchs oder einer Liste und zum Zurückgeben des Pfads jedes gefundenen ⇐ Python

[Anonymous]

Ich löse das immer wieder fast.
Ich habe einen Datensatz mit Python-Wörterbüchern, die sowohl Listen als auch Wörterbücher enthalten, die auch Listen und Wörterbücher enthalten.
Ich möchte alle Instanzen einer Teilzeichenfolge in einem der Werte finden und ich möchte wissen, welchen Pfad ich eingeschlagen habe, um sie zu finden. Ich mache ein vereinfachtes Beispiel:

Code: Select all

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

Wenn ich nach „do“ suche, möchte ich etwas wie

Code: Select all

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

Die tatsächliche Datenstruktur spielt keine Rolle. Von mir aus könnte es eine einzige lange Saite sein. Ich muss nur wissen können, dass die erste Entität (Doug) zwei Übereinstimmungen für die Teilzeichenfolge „do“ hatte und eine auf seinen Namen und eine auf seine Lebensmittelliste lautete.
Und meine tatsächlichen Daten sind ein ganzes Stück komplizierter. Ich möchte, dass mein Algorithmus mit beliebigen verschachtelten Listen und Objekten funktioniert.
Hier ist mein letzter Versuch:

Code: Select all

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

Ich bekomme [[['doug', 'name'], [['hotdog', 2], 'foods'], 0]]
Das fühlt sich an wie ein Lehrbuchproblem mit einer eleganten Antwort und das ist es, worauf ich hoffe.