Isomorphic Strings

easy 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

Best approachTime O(n)Space O(1) for a fixed alphabet

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.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * 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)
  1. Why do we need a map in both directions?