Intro
Two\$n\$-strings\$s = \langle s_1 \ldots s_n \rangle \$ and\$z = \langle z_z \ldots z_n \rangle\$ are consideredisomorphic 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 theareIsomorphic method correct.
1 Answer1
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 aset containing allvalues 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 theput method returns the previous value associated with the key (ornull), and theadd method returns a boolean value indicating if the added value was already present in a set. This makes the calls tocontainsKey,contains, andget 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;}
You mustlog in to answer this question.
Explore related questions
See similar questions with these tags.