LeetCode Notes: Isomorphic Strings

#leetcode

Question

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"

Output: true

Example 2:

Input: s = "foo", t = "bar"

Output: false

Example 3:

Input: s = "paper", t = "title"

Output: true

Constraints:

  • 1 <= s.length <= 5 * 104
  • t.length == s.length
  • s and t consist of any valid ascii character.

Solution

Analysis:

Observing isomorphic strings, two laws can be drawn:

  • If the strings on both sides are new, the condition of isomorphism is satisfied
  • If there is a recurring string, you need to ensure that the recurring string is consistent with the previous element

The specific steps are

  1. Define two objects. When traversing strings, map each string to s => t and t => s
  2. The key point is to judge whether the previous mapping relationship can be maintained when the string appears repeatedly. Of course, if it is a new one, it also meets the conditions.

Code:

/**
  * @param {string} s
  * @param {string} t
  * @return {boolean}
  */
var isIsomorphic = function(s, t) {
     // Store each string for comparison
     const sObj = {},tObj = {};
     for(let i = 0; i < s.length; i++){
         // Take out each string
         const x = s[i],y = t[i];
         // If it is the first occurrence of the character, it is stored. If it is found that all strings appear for the first time, it is an isomorphic string
         // If the characters that have appeared before, it is necessary to judge whether xy is a mutual mapping, as long as one of them is not a mapping, it is not an isomorphic string
         if((sObj[x] && sObj[x] !== y) || (tObj[y] && tObj[y] !== x)){
             return false;
         }
         // Store the first occurrence of the string
         sObj[x] = y;
         tObj[y] = x;
     }
     return true;
};

Reference

Comments