Isomorphic Strings LeetCode Solution

Problem Statement

Isomorphic Strings LeetCode Solution – 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.

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

Explanation

The key-value pairs in the dictionary are the correspondence of the letter of the first word to the letter of the second word.

For example:

a = ‘title’, b = ‘paper’
In dict:
“t” : “p”
“i” : “a”
“l” : “e”
“e” : “r”

During the loop, we check if the letter has occurred to us before, and if so, we check if it “equals” the same letter from the second word as before.

After the loop, we check that the different keys do not correspond to the same value (that is, that different letters from the first word do not equal the same letter from the second one).

1. We define a dictionary mapping_s_t which will be used to map characters in the string s to characters in the string t and another dictionary mapping_t_s which will be used to map characters in the string t to characters in the string s.
2. Next, we iterate over the two strings one character at a time.
3. Let’s assume the character in the first string is c1 and the corresponding character in the second string is c2.
   1. If c1 does not have a mapping in mapping_s_t and c2 does not have a mapping in mapping_t_s, we add the corresponding mappings in both dictionaries and move on to the next character.
   2. At this point, we expect both the character mappings to exist in the dictionaries and their values should be mapping_s_t[c1] = c2 and mapping_t_s[c2] = c1. If either of these conditions fails (c1 is not in the dictionary, c2 is not in the dictionary, unexpected mapping), we return false.
4. Return true once both the strings have been exhausted.

Code

Java Code For Isomorphic Strings

class Solution {
    public boolean isIsomorphic(String s, String t) {
        
        int[] mappingDictStoT = new int[256];
        Arrays.fill(mappingDictStoT, -1);
        
        int[] mappingDictTtoS = new int[256];
        Arrays.fill(mappingDictTtoS, -1);
        
        for (int i = 0; i < s.length(); ++i) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            
            // Case 1: No mapping exists in either of the dictionaries
            if (mappingDictStoT[c1] == -1 && mappingDictTtoS[c2] == -1) {
                mappingDictStoT[c1] = c2;
                mappingDictTtoS[c2] = c1;
            }
            
            // Case 2: Ether mapping doesn't exist in one of the dictionaries or Mapping exists and
            // it doesn't match in either of the dictionaries or both 
            else if (!(mappingDictStoT[c1] == c2 && mappingDictTtoS[c2] == c1)) {
                return false;
            }
        }
        
        return true;
    }
}

Python Code For Isomorphic Strings

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        
        mapping_s_t = {}
        mapping_t_s = {}
        
        for c1, c2 in zip(s, t):
            
            # Case 1: No mapping exists in either of the dictionaries
            if (c1 not in mapping_s_t) and (c2 not in mapping_t_s):
                mapping_s_t[c1] = c2
                mapping_t_s[c2] = c1
            
            # Case 2: Ether mapping doesn't exist in one of the dictionaries or Mapping exists and
            # it doesn't match in either of the dictionaries or both            
            elif mapping_s_t.get(c1) != c2 or mapping_t_s.get(c2) != c1:
                return False
            
        return True

Complexity Analysis for Isomorphic Strings LeetCode Solution

Time Complexity

O(N)

Space Complexity

O(1)