Check if two given strings are isomorphic to each other

Posted by N.K. Chauhan on Mar 31, 2024

Given two strings 's1' and 's2', the task is to check if these two strings are isomorphic to each other.

Two strings s1 and s2 are called isomorphic if there is a one-to-one mapping possible for every character of s1 to every character of s2 while preserving the order.

Note: All occurrences of every character in s1 should map to the same character in s2 and any character in s2 should not map to two different in s1.

Input: s1="zoo", s2="aas"
Output: false

Input: s1="wfca", s2="yssy"
Output: false

Input: s1="zhi", s2="kcz"
Output: true


Solutions

Method 1: Using Hashing

The idea is to maintain a Hash to store s1 to s2 character mapping.

In order to verify if the given strings are isomorphic, one of the following conditions should be true:

1) If the hash contains an entry for the character s1[i], the value should match s2[i]. (to make sure any character from s1 is always mapped to the same character in s2).

2) Otherwise, s2[i] should not be saved as a value. (to make sure no character from s2 is mapped to more than one character in s1).

Complexity

The time complexity of this solution is O(n+m) and space complexity is O(distinctCharacters([n,m])).

Related


Swap all occurrences of two characters to get lexicographically smallest string

Check if two strings are equal or not after processing backspace

Print all permutations of a given string

Reverse words in a given string

Find all substrings of a string in "O (n^2)" time

Power Set: Print all non-empty subsequences of a string

Check whether the given string is a palindrome

Transform One String to Another with a Minimum Number of Operations

Print all subsequences of a string

Longest Common Prefix in an Array of Strings