Isomorphic String - Getting Started / Warm Up

Problems
1

https://algo.monster/problems/isomorphic_string

2

Question: do you really need a map if you can just compare the size of the sets? I think an inherit property of two isomorphic words means that the words have the same number of unique characters. For example, egg and all, both have set(e, g) and set(a, l).

3

This code has passed
var f = str1.chars().distinct().toArray();
var s = str2.chars().distinct().toArray();
return f.length == s.length;

4

How will you validate the order of the characters?

5

the below test fails with this code as the ordering constraint is not satisfied
geg
all

6

This one line solution in Python passed:
return len(set(str_1)) == len(set(str_2))

7

You do because say you have this test case:
str_1 = “baa”
str_2 = “aab”
They both have the same number of unique characters but it’s not isomorphic because b->a and a->a

8

Tests dont work for C#. Looks like it might be doing some funky string comparison:

Output mismatch
Input
egg
all
Your Output
True
Expected Output
true

9

Looks like the Java tests aren’t quite right. The tests don’t seem to be checking for order at all.
My initial attempt at this just checked the unique character count in each word.

I thought I had it right because all tests passed.

After reading the comments, I found some others that mentioned the ordering requirement from the instructions and I realized I didn’t implement that, but still passed all tests…

One of the test cases provided is Aaron <-> Kronk. The test shows the output should be True and my code produces true.
But in reality, this one should be false.
A → K in position 0
A → R in position 1
This should return false at this point.

10

There’s a bug in the tests with C#. String comparison needs to be case insensitive. Easy fix. Right now, valid C# code returns “True”. If the test is expecting “true”, it indicates a failed test.

11

Thank you, we will fix it.

12

return len(set(str_1)) == len(set(str_2)) == len(set(zip(str_1,str_2)))

13

Lots of comments saying a one liner return test passed. Even so, I don’t think that does quite demonstrate the right knowledge of these things, for which the interviewer evaluates you for. Its really neat tho. =)

Anyway, my easy to understand solution:

    public static boolean isIsomorphic(String str1, String str2) {
        // WRITE YOUR BRILLIANT CODE HERE
        
        if (str1.length() != str2.length()) return false;
        
        HashMap<Character, Character> map = new HashMap<>();
        HashSet<Character> usedChars = new HashSet<>();
        
        int a = 0;
        int b = 0;
        while (a < str1.length() && b < str2.length()) {
            char s1 = str1.charAt(a);
            char s2 = str2.charAt(b);
            
            if (!map.containsKey(s1) && !usedChars.contains(s2)) {
                map.put(s1, s2);    
                usedChars.add(s2);
            }
            
            if (map.containsKey(s1)) {
                char tmpS2 = map.get(s1);
                if (tmpS2 != s2) return false;
            }
            else if (usedChars.contains(s2)) {
                return false;
            }
            a++;
            b++;
        }
        return true;
    }
14

With 2 hashmaps

        
        if(str1.length() != str2.length()) {
            return false;
        }
        
        final Map<Character, Character> result1 = new HashMap<>();
        final Map<Character, Character> result2 = new HashMap<>();
        
        for (int i=0; i< str1.length(); i++)  {
            
            if(result1.get(str1.charAt(i))!=null || result2.get(str2.charAt(i))!=null)
            {
                if(result1.get(str1.charAt(i)) ==null || result2.get(str2.charAt(i)) ==null)
                {
                    return false;
                }
                else if(result1.get(str1.charAt(i)) != str2.charAt(i)  || result2.get(str2.charAt(i)) != str1.charAt(i))
                {
                    return false;
                }
                else {
                    continue;
                }
            }
              result1.put(str1.charAt(i), str2.charAt(i));
              result2.put(str2.charAt(i), str1.charAt(i));
        }```
15

Solution with 2 hashmaps in python:

map12, map21 = {},{}
if len(str_1) != len(str_2): #has to be == in len otherwise there is no chance
    return False
for i in range(len(str_1)):
    c1, c2 = str_1[i], str_2[i]
    if c1 in map12:
        if map12[c1] != c2:
            return False
    else:
        map12[c1] = c2
    
    if c2 in map21:
        if map21[c2] != c1:
            return False
    else:
        map21[c2] = c1
return True
16

Java solution using streams. Commented section is for readability

    if(str1.length() != str2.length()) {
        return false;
    }
    
    return Stream.of(str1, str2)
                .map(s -> Stream.of(s.split(""))
                                .map(Function.identity())
                                .collect(Collectors.toSet()).size())
                .collect(Collectors.toSet()).size() == 1;

    /**
    Set isoStr1 = Stream.of(str1.split(""))
        .map(Function.identity())
        .collect(Collectors.toSet());
    
    Set isoStr2 = Stream.of(str2.split(""))
        .map(Function.identity())
        .collect(Collectors.toSet());
    
    return isoStr1.size() == isoStr2.size();
    **/
17

str_1 = “wowo”, str_2 = “wwoo” breaks it because there is not relation/ordering between the characters