Strings - Isomorphic Strings

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: letter 'e' and 'g' in string s can be replaced with letter 'a' and 'd' from t, since there is 1-a and 2-d's in t while preserving the order.

Input: s = "foo", t = "bar"
Output: false
Explanation: letter 'f' in string s can be replaced by 'b' letter from string t, and to replace 'o' from s we need a letter from t that appeared twice from index 1, but there are no such elements in t.

Solution using HashMap, store mapping from both strings
Solution using an array, store mapping from both strings

In this approach, we are going to store mapping from characters in s to t and from t to s and check if the mapping character from s to t matches with t to s, by doing so:

We are making sure that order is preserved.
No two characters map to the same character

For example, consider s = "egg" and t = "add"

Base for the solution is, both strings should have same length, if not we can
In the first step, we map letter p from s to letter t from t and map t from t to p from s.
Mapping from s to t
Letters from 's' Letters from 't'

e a

Mapping from t to s
Letters from 't' Letters from 's'

a e

In the second step, we map letter g from s to letter d from t and map d from t to g from s.

Mapping from s to t
Letters from 's'	Letters from 't'
e	a
g	d

Mapping from t to s
Letters from 't'	Letters from 's'
a	e
d	g

In the third step, we map letter g from s, but it already present in the map, so we can skip this.
Since we are able to add mapping from s to t and t to s with same characters, so we can return true.

Implementation

We will create a function usingHashMapStoreMapping that takes input arguments string s and t.
Base case is, if the length of s is not equal to t, then we can simply return false.
We will create two HashMaps to store characters mapping from s to t and t to s
Then, we will loop through characters from string s and add to map and at the same time add characters mapping from t to s. If mapping of characters are same in both maps are same, then the strings are isomorphic otherwise not.

import java.util.HashMap; public class IsomorphicStrings { static boolean usingHashMapStoreMapping(String s, String t) { if (s.length() != t.length()) { return false; } HashMap<Character, Character> s_map = new HashMap<>(); HashMap<Character, Character> t_map = new HashMap<>(); for(int i=0; i<s.length(); i++ ){ char s_char = s.charAt(i); char t_char = t.charAt(i); Character s_exists = s_map.get(s_char); // if mapping already exists and not equal to t_char, then we can return false if(s_exists != null && s_exists != t_char) { return false; } s_map.put(s_char, t_char); Character t_exists = t_map.get(t_char); if(t_exists != null && t_exists != s_char) { // if already exists and not equal to s_char, then we can return false return false; } t_map.put(t_char, s_char); } return true; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input string s length.
Space complexity: O(n) since we are storing the mapping into a HashMap.

This solution will work for any type of characters from input strings.

In this approach, we are going to implement the solution same as above, instead of using a HashMap we will be using an array to store the mapping. Since the input strings are going to have only ASCII characters, we will create arrays with size 128.

public class IsomorphicStrings { static boolean usingArrayToStoreMapping(String s, String t) { int[] s_map = new int[128]; int[] t_map = new int[128]; for(int i=0; i<s.length(); i++) { char s_char = s.charAt(i); char t_char = t.charAt(i); int s_exists = s_map[s_char]; if(s_exists != 0 && s_exists != t_char) { return false; } s_map[s_char] = t_char; int t_exists = t_map[t_char]; if(t_exists != 0 && t_exists != s_char) { return false; } t_map[t_char] = s_char; } return true; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input string s length.
Space complexity: O(1) since we are storing the mapping into an array of fixed size of 128.

Above implementations source code can be found at GitHub link for Java code

Contents

Implementation

Complexity Analysis:

Complexity Analysis: