Isomorphic Strings Function Always Returns True-CodePudding

I am attempting the Isomorphic Strings problem on LeetCode and am having issues with my current solution. I'm sure there are plenty of answers on exactly how to complete this problem, but I would really prefer to finish it through my own thought process before learning the best possible way to do it. For reference, here is the problem: https://leetcode.com/problems/isomorphic-strings/?envType=study-plan&id=level-1

This is my code as it is right now:

var isIsomorphic = function(s, t) {
    
    const map = new Map();
    const array1 = [...s];
    const array2 = [...t];
    
    for (i = 0; i < s.length; i  ) {
        if ((map.has(array1[i]) === true) && (map.has(array2[i]) === true)) {
            if (map.get(array1[i]) !== array2[i]) {
                return false;
            } else {
                continue;
            }
        } else if (map.has(array1[i]) === false) {
            map.set(array1[i], array2[i]);
        }
    }
    return true;    
};

It's messy but I can't figure out why it isn't giving me the desired results. Right now, it seems to always return true for any given values, even though I have the initial if statement to return false if it ever comes across previously-mapped values that don't match. Am I missing something obvious? This is my first question on SA, so I apologize if the format is wrong.

CodePudding user response：

The map is set like:

map.set(array1[i], array2[i]);

The key is the character in the first string, and the value is the corresponding character in the second string. So, when iterating over a new character, checking map.has will only make sense if the character being passed is from the first string; doing map.has(array2[i]) === true)) does not test anything useful, because the second string's characters are not keys of the Map.

You need to perform two tests: that the 1st string's character corresponds to the 2nd string's character (which you're doing right), and that the 2nd string's character is not already set to a different 1st string's character (which needs to be fixed). For this second condition, consider having another Map that's the reverse of the first one - the keys are the characters from the 2nd string, and the values are the characters from the 1st string. (You don't have to have another Map - you could also iterate through the .entries of the first, check that, for every entry's value that matches the 2nd character, the entry's key matches the 1st - but that could feel a bit messy.)

Cleaning up your code some, there's also no need to turn the strings into arrays, and === true can be omitted entirely, and the i variable should be declared with let.

You also might want to check if the length of the first string is equal to the length of the second.

var isIsomorphic = function(s1, s2) {
    if (s1.length !== s2.length) return false;
    const map1to2 = new Map();
    const map2to1 = new Map();
    for (let i = 0; i < s1.length; i  ) {
        // Check that s1 here corresponds to s2
        if (map1to2.has(s1[i]) && map1to2.get(s1[i]) !== s2[i]) {
            return false;
        }
        // And that s2 here doesn't correspond to any other s1
        if (map2to1.has(s2[i]) && map2to1.get(s2[i]) !== s1[i]) {
            return false;
        }
        map1to2.set(s1[i], s2[i]);
        map2to1.set(s2[i], s1[i]);
    }
    return true;
};
console.log(isIsomorphic('aa', 'bb'));
console.log(isIsomorphic('aa', 'ba'));
console.log(isIsomorphic('badc', 'baba'));