Checking for string isomorphism in Java

Question

Intro

Two \$n\$-strings \$s = \langle s_1 \ldots s_n \rangle \$ and \$z = \langle z_z \ldots z_n \rangle\$ are considered isomorphic if and only if there exists a bijection \$f\$ such that for all \$s_i\$ we have \$f(s_i) = z_i\$. This Java class provides a method for checking whether the two input strings are isomorphic:

Code

io.github.coderodde.string.util.StringIsomorphismChecker.java:

package io.github.coderodde.string.util;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * This class provides a static method for testing whether the two input strings
 * are anagrams.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.0.0 (Sep 10, 2025)
 * @since 1.0.0 (Sep 10, 2025)
 */
public final class StringIsomorphismChecker {
    
    private StringIsomorphismChecker() {
        
    }

    /**
     * Tests whether the two input strings are <i>isomorphic</i>. Two strings 
     * {@code s} and {@code z} are isomorphic if there exists a one-to-one 
     * mapping between the characters of {@code s} and the characters of 
     * {@code z} such that replacing each character in {@code s} according to
     * this mapping produces {@code z}.
     * 
     * @param s the first string.
     * @param z the second string.
     * @return {@code true} if and only if the two input strings are isomorphic.
     */
    public static boolean areIsomorphic(String s, String z) {
        
        Objects.requireNonNull(s, "The first input string is null");
        Objects.requireNonNull(z, "The second input string is null");
        
        if (s.length() != z.length()) {
            return false;
        }
        
        Map<Character, Character> isomorphism1 = new HashMap<>();
        Map<Character, Character> isomorphism2 = new HashMap<>();
        
        for (int i = 0; i < s.length(); ++i) {
            char chs = s.charAt(i);
            char chz = z.charAt(i);
            
            if (!isomorphism1.containsKey(chs)) {
                isomorphism1.put(chs, chz);
            }
            
            if (!isomorphism2.containsKey(chz)) {
                isomorphism2.put(chz, chs);
            }
            
            if (isomorphism1.get(chs) != chz ||
                isomorphism2.get(chz) != chs) {
                return false;
            }
        }
        
        return true;
    }
}

io.github.coderodde.string.util.StringIsomorphismCheckerTest.java:

package io.github.coderodde.string.util;

import static io.github.coderodde.string.util.StringIsomorphismChecker.areIsomorphic;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import org.junit.Test;

/**
 * This test class provides unit tests for checking the class 
 * {@link io.github.coderodde.string.util.StringIsomorphismChecker}.
 * 
 * @version 1.0.0 (Sep 11, 2025)
 * @since 1.0.0 (Sep 11, 2025)
 */
public class StringIsomorphismCheckerTest {
    
    private static final int ITERATIONS = 1_000;
    private static final int MAX_STRING_LENGTH = 30;
    private static final Map<Character, Character> ISOMORPHISM_MAP = 
            new HashMap<>();
    
    static {
        ISOMORPHISM_MAP.put('0', 't');
        ISOMORPHISM_MAP.put('1', 'a');
        ISOMORPHISM_MAP.put('2', 'q');
        ISOMORPHISM_MAP.put('3', 'o');
        ISOMORPHISM_MAP.put('4', 'p');
        ISOMORPHISM_MAP.put('5', 'l');
        ISOMORPHISM_MAP.put('6', 'm');
        ISOMORPHISM_MAP.put('7', 'i');
        ISOMORPHISM_MAP.put('8', 'r');
        ISOMORPHISM_MAP.put('9', 'x');
    }
    
    @Test
    public void stressTestStringIsomorphism() {
        Random random = new Random(13L);
        
        for (int iteration = 0; iteration < ITERATIONS; ++iteration) {
            int stringLength = 1 + random.nextInt(MAX_STRING_LENGTH);
            String s = getRandomString(stringLength, random);
            String z = mapString(s);
            
            assertTrue(areIsomorphic(s, z));
        }
    }
    
    @Test
    public void nonIsomorphicCases() {
        assertFalse(areIsomorphic("a", "ab"));
        assertFalse(areIsomorphic("ab", "aa"));
        assertFalse(areIsomorphic("bab", "ccx"));
    }
    
    private static String getRandomString(int length, Random random) {
        StringBuilder sb = new StringBuilder(length);
        
        for (int i = 0; i < length; ++i) {
            sb.append('0' + random.nextInt(10));
        }
        
        return sb.toString();
    }
    
    private static String mapString(String s) {
        StringBuilder sb = new StringBuilder(s.length());
        
        for (int i = 0; i < s.length(); ++i) {
            sb.append(ISOMORPHISM_MAP.get(s.charAt(i)));
        }
        
        return sb.toString();
    }
}

Critique request

As always, I am eager to receive constructive commentary on my work. My primary concern is whether the areIsomorphic method correct.

Answer 1

The logic looks correct to me, but can be simplified a bit. Instead of two maps it suffices to maintain one map (representing the isomorphism constructed so far) and a set containing all values encountered so far.

    Map<Character, Character> isomorphism = new HashMap<>();
    Set<Character> values = new HashSet<>();
    
    for (int i = 0; i < s.length(); ++i) {
        char chs = s.charAt(i);
        char chz = z.charAt(i);
        
        if (!isomorphism.containsKey(chs)) {
            if (values.contains(chz)) {
                return false;
            }
            isomorphism.put(chs, chz);
            values.add(chz);
        } else if (isomorphism.get(chs) != chz) {
            return false;
        }
    }

    return true;
}

This can be further simplified by using the fact that the put method returns the previous value associated with the key (or null), and the add method returns a boolean value indicating if the added value was already present in a set. This makes the calls to containsKey, contains, and get obsolete (and might therefore be more efficient):

    Map<Character, Character> isomorphism = new HashMap<>();
    Set<Character> values = new HashSet<>();
    
    for (int i = 0; i < s.length(); ++i) {
        char chs = s.charAt(i);
        char chz = z.charAt(i);
    
        Character previous = isomorphism.put(chs, chz);
        if (previous == null) {
            // chs -> chz is a new mapping, check if the same value has not been used before:
            if (!values.add(chz)) {
                return false;
            }
        } else if (previous != chz) {
            // chs was already mapped to a different character.
            return false;
        }
    }

    return true;
}