Expand a Template With Variables

Medium

You have a set of variables, each entry a pair [name, value]. A name is a single uppercase English letter. A value is a string that may contain references to other variables written as %X%, where X is a variable name. You also get a template: one or more references to distinct variables, joined by _. Replace every reference %X% with the value of X, and keep going until no references remain (values get expanded too). Return the resulting string. The variables have no circular dependencies, and every reference points to an existing variable.

Example 1

variables=[['N', 'anna'], ['C', 'paris']], template='%N%_%C%' → 'anna_paris'

%N% becomes "anna" and %C% becomes "paris".

Example 2

variables=[['G', 'hi_%U%'], ['U', 'bob'], ['D', '%G%%U%']], template='%D%_%U%_%G%' → 'hi_bobbob_bob_hi_bob'

%G% expands to "hi_bob", so %D% is "hi_bob" + "bob" = "hi_bobbob".

Example 3

variables=[['Z', '42']], template='%Z%' → '42'

Constraints

1 ≤ len(variables) ≤ 10
Variable names are distinct uppercase English letters
Each value is a non-empty string of at most 8 characters: lowercase letters, digits, _ and %X% references
template consists of %X% references to distinct variables joined by _
There are no circular dependencies

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph Topological Sort Array Hash Table String