Detecting if two given strings are isomorphic using Java data structures

Question

So I have written the following code and it works for various same length isomorphic strings I have tried. However I am not sure what are some time complexity improvements and coding tweaks that could be applied to the code:

/**
 * Created by mona on 5/26/16.
 */
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Collections;
public class IsomorphicStrings {
 //the words "abca" and "zbxz" are isomorphic
 //aabc a(2) b(1) c(1)
 //zzbx z(2) b(1) x(1)
 //my algorithm
 //create a sorted hashmap on value
 //check to see if two hashmap are equal based on their value set
 //assuming two isomorphic strings are of the same length
 public static boolean areIsomorphic(String s1, String s2) {
 Map<Character, Integer> freqMap1 = new HashMap<>();
 Map<Character, Integer> freqMap2 = new HashMap<>();
 for (int i=0; i<s1.length(); i++) {
 if (freqMap1.containsKey(s1.charAt(i))) {
 int freq1 = freqMap1.get(s1.charAt(i));
 freqMap1.put(s1.charAt(i), freq1 + 1);
 } else {
 freqMap1.put(s1.charAt(i), 1);
 }
 }
 for (int i=0; i<s2.length(); i++) {
 if (freqMap2.containsKey(s2.charAt(i))) {
 int freq2 = freqMap2.get(s2.charAt(i));
 freqMap2.put(s2.charAt(i), freq2 + 1);
 }
 else {
 freqMap2.put(s2.charAt(i), 1);
 }
 }
 List<Integer> freqList1 = new ArrayList<>();
 List<Integer> freqList2 = new ArrayList<>();
 for (Map.Entry entry: freqMap1.entrySet()) {
 freqList1.add((Integer) entry.getValue());
 }
 for (Map.Entry entry: freqMap2.entrySet()) {
 freqList2.add((Integer) entry.getValue());
 }
 Collections.sort(freqList1);
 Collections.sort(freqList2);
 return freqList1.equals(freqList2);
 }
 public static void main(String[] args) {
 String s1="abca";
 String s2="zbxz";
 System.out.println(areIsomorphic(s1, s2));
 }
}

/* side note: can isomorphic strings be of different lengths? Then what algorithm do you suggest? */

• Mona Jalal: can you explain why there was two vote downs on this question?

Answer 1

I see that your coding style is improving. What comes to the concept of isomorphism, two strings of different length should never be considered isomorphic due to the definition of isomorphism:

Two strings \$S_1 = c_1 c_2 \dots c_n\$ and \$S_2 = c'_1 c'_2 \dots c'_n\$ are isomorphic if and only if there exists a bijection \$f\$ such that \$c'_i = f(c_i)\$ for all \$i = 1, 2, \dots, n\$.

What comes to your algorithm, you could rewrite it a little bit more succintly:

public static boolean areIsomorphic(String s1, String s2) {
 if (s1.length() != s2.length()) {
 return false;
 }
 Map<Character, Integer> frequencyMap1 = new HashMap<>();
 Map<Character, Integer> frequencyMap2 = new HashMap<>();
 for (char c : s1.toCharArray()) {
 frequencyMap1.put(c, frequencyMap1.getOrDefault(c, 0) + 1);
 }
 for (char c : s2.toCharArray()) {
 frequencyMap2.put(c, frequencyMap2.getOrDefault(c, 0) + 1);
 }
 List<Integer> freqList1 = new ArrayList<>(frequencyMap1.values()); 
 List<Integer> freqList2 = new ArrayList<>(frequencyMap2.values());
 Collections.sort(freqList1);
 Collections.sort(freqList2);
 return freqList1.equals(freqList2);
}

Hope that helps.

• 200_success: You have simplified the implementation but preserved the error in the algorithm: this function tests whether the inputs are isomorphic anagrams of each other.

Answer 2

Your build two HashMap<Character, Integer>, then two ArrayList<Integer>, then sort the lists, then compare the lists. Your logic is too complicated, I think. Furthermore, you aren't taking advantage of the symmetry in the problem — nearly every line of code appears in duplicate. Even worse, the code doesn't even do what you claim; rather, it tests whether the inputs are isomorphic anagrams of each other.

Going by the definition, we can just build a character-to-character map from one string to the other, and fail as soon as we encounter an unexpected character. This should be O(n), and possibly faster if a mismatch is detected early.

The code works equally well on any pair of CharSequences, not just Strings, so we might as well generalize.

import java.util.HashMap;
import java.util.Map;
public class IsomorphicStrings {
 public static boolean areIsomorphic(CharSequence s1, CharSequence s2) {
 return isSurjective(s1, s2) && isSurjective(s2, s1);
 }
 private static boolean isSurjective(CharSequence s1, CharSequence s2) {
 if (s1.length() != s2.length()) return false;
 Map<Character, Character> surjection = new HashMap<>();
 for (int i = 0; i < s1.length(); i++) {
 char c1 = s1.charAt(i);
 char c2 = s2.charAt(i);
 Character prev = surjection.put(c1, c2);
 if (prev != null && prev != c2) {
 return false;
 }
 }
 return true;
 }
 public static void main(String[] args) {
 System.out.println(areIsomorphic(args[0], args[1]));
 }
}

• 200_success: Related answer in Ruby

Answer 3

/* Sorry for the above post but in corner test cases my algorithm failed. Here's the complete non-failing algorithm */

/**
 * Created by mona on 5/26/16.
 */
import java.util.Map;
import java.util.LinkedHashMap;
import java.util.ArrayList;
import java.util.Arrays;
public class IsomorphicStrings {
 //the words "abca" and "zbxz" are isomorphic
 public static boolean areIsomorphic(String s1, String s2) {
 Map<Character, ArrayList<Integer>> charPos1 = new LinkedHashMap<>();
 Map<Character, ArrayList<Integer>> charPos2 = new LinkedHashMap<>();
 for (int i=0; i<s1.length(); i++) {
 if (charPos1.containsKey(s1.charAt(i))) {
 charPos1.get(s1.charAt(i)).add(i);
 } else {
 charPos1.put(s1.charAt(i), new ArrayList<>(Arrays.asList(i)));
 }
 }
 for (int i=0; i<s2.length(); i++) {
 if (charPos2.containsKey(s2.charAt(i))) {
 charPos2.get(s2.charAt(i)).add(i);
 } else {
 charPos2.put(s2.charAt(i), new ArrayList<>(Arrays.asList(i)));
 }
 }
 return new ArrayList<>(charPos1.values()).equals(new ArrayList<>(charPos2.values()));
 //return freqMap1.values().equals(freqMap2.values()); won't work
 }
 public static void main(String[] args) {
 String s1="foo";
 String s2="app";
 System.out.println(areIsomorphic(s1, s2));
 }
}

• coderodde: Could you write me the two strings that made your algorithm fail?
• Mona Jalal: The one I have written as answer is correct. The one in the question fails with "abb" and "bab" that is why I am using LinkedHashMap
• coderodde: That's odd: I copy pasted your original algorithm and it returns true for abb and bab.
• janos: @MonaJalal on leetcode you can use everything from the JDK, but some classes are not imported by default, so you need to add import java.util.LinkedHashMap; explicitly
• janos: @coderodde you need the LinkedHashMap to guarantee sorting order. HashMap doesn't guarantee that, but with short strings like "abb" and "bab" you might get the right ordering simply by chance. The ordering of elements in a HashMap may vary with JVM implementation and version