Skills101
← All coding problems

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 q lines: two words a b of 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).

Loading editor…

Log in to run and submit your code — it's free.