Given two strings, A and B, determine if they are isomorphic. Isomorphic means that for every character in string one, you can replace it with a matching character in string two, such that every occurrence of the same character gets replaced with the same character in the other string. Write a function called areIsomorphic that takes in string one and string two as the inputs and returns true if the strings are isomorphic and false if they are not.

Video Solution

Solution Walkthrough

function areIsomorphic(str1, str2) {
  if (str1.length !== str2.length) {
    return false;
  }

  const map = new Map();

  for (let i = 0; i < str1.length; i++) {
    const char1 = str1[i];
    const char2 = str2[i];

    if (!map.has(char1)) {
      map.set(char1, char2);
    } else if (map.get(char1) !== char2) {
      return false;
    }
  }

  return true;
}

We start by checking if the lengths of both strings are equal. If not, we can return false because two strings of different lengths can never be isomorphic.

Next, we initialize a Map to store the character mappings from string one to string two. We will use the map to check if a character has already been mapped and to map new characters.

We then loop through each character in the strings and check if the character from string one has already been mapped. If not, we add it to the map with the corresponding character in string two. If the character from string one has already been mapped, we check if the corresponding character from string two matches the previous mapping. If not, we can immediately return false because the strings are not isomorphic.

Finally, if we loop through the entire strings and all character mappings match, we can return true because the strings are isomorphic.

Big O Complexity Analysis: The time complexity of this solution is O(n) because we are looping through each character in both strings once. The space complexity is also O(n) because we may need to store all characters in string one and their corresponding characters in string two in the map. However, in the worst case scenario where every character is unique, we would need to store all characters in both strings, leading to a space complexity of O(2n), which simplifies to O(n).

The use of a Map helps us achieve this time complexity as it allows constant time lookups and insertions.

Final Code Output:

console.log(areIsomorphic("abc", "def")); // true
console.log(areIsomorphic("aa", "ab")); // false
console.log(areIsomorphic("aa", "bb")); // true