Isomorphic Strings
Problem
Two words are isomorphic if you can replace the letters of the first word to get the second word, where every letter always maps to the same letter and two different letters never map to the same letter. Print true or false.
Constraints
- 1 <= length <= 10^5
Examples
Input
egg add
Output
true
Input
foo bar
Output
false
Solutions
One map is not enough: foo and bar would pass the forward check, and ab to aa needs the backward map to be rejected. The mapping must be one-to-one.
/*
* Problem : Process two words.
* Input : Two words separated by a space.
* Output : true or false.
* Approach: Two maps.
* Time : O(n)
* Space : O(1) for a fixed alphabet
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static boolean solve(String a, String b) {
// Step 1: Words of different length cannot be isomorphic.
if (a.length() != b.length()) {
return false;
}
// Step 2: Keep two maps: a-letter to b-letter, and b-letter to a-letter. Both must stay consistent.
java.util.Map<Character, Character> forward = new java.util.HashMap<>();
java.util.Map<Character, Character> backward = new java.util.HashMap<>();
for (int i = 0; i < a.length(); i++) {
char x = a.charAt(i);
char y = b.charAt(i);
// Step 3: If a letter was mapped before to something else, the words are not isomorphic.
if (forward.containsKey(x) && forward.get(x) != y) {
return false;
}
if (backward.containsKey(y) && backward.get(y) != x) {
return false;
}
forward.put(x, y);
backward.put(y, x);
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String a = scanner.next();
String b = scanner.next();
System.out.println(solve(a, b));
}
}
Hints (1)
- Why do we need a map in both directions?