Leetcode 205. Isomorphic Strings

Problem Explanation

This problem is asking youto check if two given strings are isomorphic. Two strings are isomorphic when all characters in string s can be replaced to get string t, with the condition that each character keeps the same order of appearance in both strings. Additionally, characters can only map once to another character, however, a character can map to itself.

Walk Through an Example

Let's take a look at the example s = "egg" and t = "add". We can see the first character in s is 'e' which corresponds to 'a' in t. The second and third characters in s are 'g', which corresponds to 'd' in t. Therefore, we can now safely say that s is isomorphic to t.

Solution Approach

To solve this problem, a HashMap data structure can be used to map characters from string s to string t. For each character in string s, it is checked whether there is a mapping of this character to another character in string t. If no mapping exists, it is added to the map. If a mapping exists but it doesn't match with the current character in string t, then return false.

1e.g., s = "egg"
2      t = "add"
3      
4      Map:
5      e -> a
6      g -> d
7
8      s = "foo"
9      t = "bar"
10  
11      Map:
12      f -> b
13      o -> a
14      

Here, the function returns false because the second character in s already has a mapping but it does not match with the second character in t.

Python Solution

1
2python
3class Solution:
4    def isIsomorphic(self, s: str, t: str) -> bool:
5        map_s_t = {}
6        map_t_s = {}
7
8        for i in range(len(s)):
9            if (s[i] not in map_s_t) and (t[i] not in map_t_s):
10                map_s_t[s[i]] = t[i]
11                map_t_s[t[i]] = s[i]
12            elif t[i] != map_s_t.get(s[i]) or s[i] != map_t_s.get(t[i]):
13                return False
14        return True

Java Solution

1
2java
3import java.util.*;
4class Solution {
5    public boolean isIsomorphic(String s, String t) {
6        HashMap<Character, Character> map = new HashMap<>();
7        for (int i = 0; i < s.length(); i++) {
8            char sChar = s.charAt(i);
9            char tChar = t.charAt(i);
10            if (map.containsKey(sChar)) {
11                if (map.get(sChar) != tChar) {
12                    return false;
13                }
14            } else {
15                if (map.containsValue(tChar)) {
16                    return false;
17                }
18                map.put(sChar, tChar);
19            }
20        }
21        return true;
22    }
23}

Javascript Solution

1
2javascript
3var isIsomorphic = function(s, t) {
4    const map = new Map();
5    for (let i = 0; i < s.length; i++) {
6        if (!map.has(s[i])) {
7            if (Array.from(map.values()).includes(t[i])) return false;
8            map.set(s[i], t[i]);
9        } else if (map.get(s[i]) !== t[i]) return false;
10    }
11    return true;
12};

C++ Solution

1
2c++
3class Solution {
4public:
5    bool isIsomorphic(string s, string t) {
6        unordered_map<char, char> map_s_t;
7        unordered_map<char, char> map_t_s;
8
9        for (int i = 0; i < s.length(); i++) {
10            if (map_s_t.count(s[i]) == 0 && map_t_s.count(t[i]) == 0) {
11                map_s_t[s[i]] = t[i];
12                map_t_s[t[i]] = s[i];
13            } else if (t[i] != map_s_t[s[i]] || s[i] != map_t_s[t[i]]) {
14                return false;
15            }
16        }
17        return true;
18    }
19};

C# Solution

1
2csharp
3public class Solution {
4    public bool IsIsomorphic(string s, string t) {
5        Dictionary<char,char> Smap = new Dictionary<char,char>();
6        Dictionary<char,char> Tmap = new Dictionary<char,char>();
7
8        for (int i = 0; i < s.Length; i++){
9            char sChar = s[i];
10            char tChar = t[i];
11
12            if (Smap.ContainsKey(sChar) && Smap[sChar] != tChar) {
13                return false;
14            }
15
16            if (Tmap.ContainsKey(tChar) && Tmap[tChar] != sChar) {
17                return false;
18            }
19
20            Smap[sChar] = tChar;
21            Tmap[tChar] = sChar;
22        }
23        return true;
24    }
25}

In these solutions, we use two dictionaries/map to map the characters in string s and t. If a character in string s is not in the map and character from string t also not in the map, then add the corresponding characters to the maps. If not, then check whether the current character matches the mapped character. If not, then return false. If it matches continue with the next character. If all characters match their mapped characters then return true.This algorithm runs in O(n) time since we are simply iterating a single time over the strings of length 'n', performing constant operations with each iteration. It also has O(n) space since at worst case we will be storing all characters of the strings into the hashmap.

These solutions offer a straightforward and efficient way to solve this problem with great time complexity. From these examples, you can clearly appreciate the power of hashmaps and how they can be used to map relationships and pairs of data. As always, make sure you understand the problem thoroughly before deciding on which data structures and methods to use. Always pay attention to the time and space complexity of your algorithms to ensure you arrive at the most optimized solution.

As a challenge, you can try to think about how the solution to determine isomorphism could change if the condition "Characters can only map once to another character" is not given.+

This will surely make you delve deeper into the nature of hashmaps and perhaps come up with a more complex but equally optimized solution. Happy Coding!