You are not logged in. Please login at to post your questions!


string to number

You need to pass a secret key to your friend, which consists of all numbers but you don't trust the carrier. So, instead you pass a character string. You come up with a set of rules to map the string to the original key.

  1. Each character in the string should be replaced as the rule suggests.

  2. If the right hand side of the rule is a character, then this character should again be replaced till we find a number. The range of the numbers lies between 1 and 9.

  3. If no such number could be found but a cycle is detected, each such character should be replaced with 0. Note that this includes numbers which map to themselves (self loops).

  4. If no cycle is detected and no number replacement could be found, you should output -1.

  5. If a character appears in the test string which does not appear in the mapping, output -1. Input

First line of input contains a single integer T, the number of test cases. T test cases will follow. Each test case begins with a mapping. A mapping begins with a number N, the number of rules. Then N lines, each line in the form of A B will follow, where A is to be replaced by B. Then follows an integer K, the number of test strings. Then K lines follow, each line consisting of a test string. Output

For each test case, print on the first line # followed by the test case number, followed by the replacement string for every test string. Solution Templates

In the solution templates provided, complete the function whose signature is

C / C++ void decode (int n, char orig[26], char mapped[26], int k, char inputs[32][128], char outputs[32][128])

Java public static void decode(int n, char[] orig, char[] mapped, int k, String[] inputs, String[] outputs)

'n' is the number of mappings. 'orig' and 'mapped' store the original and mapped values respectively. 'k' is the number of queries. 'inputs' are the encoded strings. It is expected that you will store your answers in 'outputs', which is then printed by the template. Note that in JAVA, do not allocate outputs. It will be allocated, and hence put your answers in outputs.

Note: You are allowed to edit the code as you please. Add / delete headers. Add / delete methods. And so on.. So long as your final code solves the problem with Input and Output as described above. You may submit your own code, without using the template at all. Constraints

1<=T<=100 1<=N<=26 The left hand side of the rule consists of a single lowercase character The right hand side of the rule consists of a single lowercase character or a single non zero digit. No character will map to more than one character, i.e. you cannot have a situation where a maps to both b and c.

Sample Input

1 10 a b b c c a d e e f f 9 g h i j j 7 k p 3 abcdefij kabc aza

Sample Output


00099977 -1 -1


String 1:a, b, and c form a cycle, and d maps to e, which maps to f, which maps to 9, and i maps to j, which maps to 7.

String 2: k maps to p, which maps to no nothing else. Hence -1.

String 3: The character z doesn't appear in the mapping. Hence -1.

asked 11 Oct, 16:14

sagarkoyani's gravatar image

accept rate: 0%


Please provide the problem source so that we know this is not from a live contest.

(11 Oct, 17:21) meooow ♦6★

This link might help!!


answered 12 Oct, 10:02

kunnu120's gravatar image

accept rate: 6%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 11 Oct, 16:14

question was seen: 97 times

last updated: 12 Oct, 10:02