Isomorphic Strings
easyStrings II+10 XPTime limit 2s
Two words of the same length are isomorphic if you can get the second by consistently replacing letters of the first: every occurrence of a letter must turn into the same letter, and two different letters must never turn into the same letter. egg/add are isomorphic (e→a, g→d), but foo/bar are not (o would have to become both a and r), and neither are ab/aa.
Input:
- line 1:
q - next
qlines: two wordsa bof equal length (lowercase letters)
Output: q lines — true or false.
Constraints: 1 ≤ q ≤ 10⁴, 1 ≤ length ≤ 10⁴, total length of all words ≤ 4·10⁵.
Think about it: keep two maps — a → b and b → a. Walk both words together; if a letter is already mapped to something else (in either direction), the answer is false.
Sample input 1
3 egg add foo bar paper title
Sample output 1
true false true
Sample input 2
1 ab aa
Sample output 2
false
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).