Company: Google
Difficulty: medium
Expand Template You are given `n` key-value mappings and a source string. Inside the source string, any substring enclosed in a pair of percent signs, such as `%key%`, is a **placeholder**: it must be replaced by the value that `key` maps to. A mapped value may itself contain placeholders, so replacements have to be resolved recursively until no placeholder is left. Print the fully expanded source string. Print `ERROR` instead if either of the following happens while resolving: a placeholder names a key that is not present in the mappings, or resolving the placeholders runs into a cycle, that is, expanding some key requires expanding that same key again. Input Format The first line contains the integer `n`, the number of mappings. The next `2 * n` lines describe the mappings, two lines each: the key on the first line and its value on the second. A value may be an empty line. The last line contains the source string. Output Format Print one line: the fully expanded source string, or `ER