Алгоритм задачи, решение для переменных в словаре

Question

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

Given: {"a": "12.x.y.3", "x": "4", y: "x.x"}
Output: {"a": "12.4.4.4.3", "x": "4", y: "4.4"}

Думая о лучшем способе сделать это.Подход, который я придумал, заключался в переборе ключей, и каждый раз, когда мы сталкиваемся с нецелым символом, повторяемся, пока не достигнем целочисленного значения.

Буду признателен за любые другие идеи / псевдокод для эффективного подхода (в зависимости от сложности времени).

Answer 1

Построить ориентированный ациклический граф с каждым ключом в качестве узла и переходами от одного ключа к другому, если первому требуется значение второго.Так что в вашем примере будут ниже края:

(a-> x), (a-> y), (y-> x)

Now топологически сортировать график.Который в этом случае будет [a,y,x], то есть конечные узлы, те с целочисленными значениями будут помещены последними.Теперь, если вы начнете выполнять итерацию с конца для заполнения словаря output, вы найдете для любого ключа все остальные ключи, от которых он зависит, уже были преобразованы в int.Таким образом, избавляя вас от многократного повторения одного и того же ключа.

Или, вы знаете, вы можете просто использовать динамическое программирование для запоминания повторных вызовов:)