Собрать ключи словаря в отдельный список по условию

Question

Имеется словарь. Ключи НЕ те, что в примере. Значения в словаре - либо словари, либо текст.

Необходимо в отдельные списки собрать ветку ключей от самого корня до ключа, имеющего текстовое значение. Списки с ключами, так же необходимо собрать в итоговом списке.

Вижу реализацию с помощью рекурсии. Понимаю, что необходимо использовать функцию проверки класса. Но не понимаю как именно.

Вот, что я пытаюсь сделать:

dict1 = {'1':{'2':{'3':'text'},'4':{'5':{'6':'text'},'7':'text'}},'8':{'9':{'10':'text'}}}
    
general_list = []
def search_keys(dict1, list_key=[]):
    for key, value in dict1.items():
        list_key.append(key)
        if isinstance(value, dict):
            search_keys(value, list_key)
        elif isinstance(value, str):
            general_list.append(list_key.copy())
            list_key.clear()
    return general_list
    
print(search_keys(dict1))

Первый проход ключи собирает. Начиная со второго, все идёт не так:

[['1','2','3'],['4','5','6'],['7'],['8','9','10']]

Вот, что должно получиться:

[['1','2','3'],['1','4','5','6'],['1','4','7'],['8','9','10']]

Answer 1

Вы слишком лихо чистите list_key, сразу стираете его целиком. А в данном вызове функции нужно убирать только те данные, которые вы в него добавили: list_key.append(key)/list_key.pop():

general_list = []
def search_keys(dict1, list_key=[]):
    for key, value in dict1.items():
        list_key.append(key)
        if isinstance(value, dict):
            search_keys(value, list_key)
        elif isinstance(value, str):
            general_list.append(list_key.copy())
            # list_key.clear()                       # убрано
        list_key.pop()                               # добавлено
    return general_list
    
print(search_keys(dict1))

Но всё можно сделать гораздо проще. Обходим словарь рекурсивно, формируем списки. Производительность не самая великолепная, но если у вас не будет словарей глубиной в тысячи вложений, вы не узнаете что что-то тормозит:

def search(d):
    if isinstance(d, dict):
        for k, v in d.items():
            for lst in search(v):
                yield [k] + lst
    else:
        yield []


dict1 = {
    '1': {'2': {'3': 'text'},'4': {'5': {'6': 'text'},'7': 'text'}},
    '8': {'9': {'10': 'text'}}
}
for lst in search(dict1):
    print(lst)

$ python search.py
['1', '2', '3']
['1', '4', '5', '6']
['1', '4', '7']
['8', '9', '10']

Если производительность на очень глубоких словарях вас волнует, есть более сложный вариант с оптимальной производительностью. Отличается только способ построения списков ключей: раньше они строились последовательными конкатенациями (за квадрат от глубины словаря), теперь накапливаются на месте (за линию) при рекурсивном спуске вниз. Этот вариант очень близок к вашему, те же строительные блоки соединены по-другому:

def search(d):

    def search(d, path):
        if isinstance(d, dict):
            for k, v in d.items():
                path.append(k)
                yield from search(v, path)
                path.pop()
        else:
            yield path[:]

    return search(d, [])

До сих пор все решения рекурсивные, то есть больше тысячи вложений словарей они обрабатывать не будут. Итеративное решение снимет это ограничение. stack хранит итераторы по вложенным словарям. В path строится ответ:

def search(d):
    stack = [iter(d.items())]
    path = [None]
    while stack:
        for k, v in stack[-1]:
            path[-1] = k
            if isinstance(v, dict):
                stack.append(iter(v.items()))
                path.append(None)
            else:
                yield path[:]
            break
        else:
            stack.pop()
            path.pop()

БЛОГ НА HUSL

Собрать ключи словаря в отдельный список по условию

Ответы (1 шт):