Isomorphic Strings — Leetcode #205

Isomorphic Strings — Leetcode #205

problem links: leetcode, geekforgeeks.

Problem Statement

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:

Example 2:

Example 3:

Constraints:

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

Intuition

The question asks us to find whether the strings are isomorphic or not, that is another way to say if a one-to-one mapping is possible in strings s and t.

for example,

• String 1: “ABC”
• String 2: “XYZ”

In this example, the character ‘A’ in String 1 corresponds to the character ‘X’ in String 2, the character ‘B’ corresponds to ‘Y’, and so on.

Let’s see another example,

• String 1: “abcdefg”
• String 2: “1122333”

In this example, the character ‘a’ and ‘b’ in String 1 corresponds to the character ‘1’ in String 2, the character ‘c’ and ‘d’ corresponds to ‘2’, and so on.

In this case, also it is not one-to-one mapping as multiple characters in String 1 correspond to a single character in String 2

So, we can use a hashmap to map the characters of one string to another and check if a one-to-one mapping is possible or not.

Approach

1. Declare a map data structure and store the size of the string in a variable n.
2. Initialize a loop from 0 to n-1, where i is the loop control variable.
3. check if the s[i] is mapped to some character or not, if it is not mapped then assign it to t[i].
4. if it is already mapped then check if the one-to-one relationship is maintained, if not return false.

Solution

c++

class Solution {
public:

    bool checkIsomorphic(string s, string t){
        
        unordered_map<char, int> map;
        int n = s.size();

        for(int i=0;i<n;i++){

            char u = s[i];
            char v = t[i];

            if(map.find(u) == map.end()){
                map[u] = v;
            }else{
                if(map[u] == v) 
                    continue;
                else
                    return false;
            }
        }

        return true;
    }

    bool isIsomorphic(string s, string t) {

        return checkIsomorphic(s, t) && checkIsomorphic(t, s);
        
    }
};

Java

class Solution {

    public boolean checkIsomorphic(String s, String t) {
        Map<Character, Character> map = new HashMap<>();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            char u = s.charAt(i);
            char v = t.charAt(i);

            if (!map.containsKey(u)) {
                map.put(u, v);
            } else {
                if (map.get(u) == v) {
                    continue;
                } else {
                    return false;
                }
            }
        }

        return true;
    }


    public boolean isIsomorphic(String s, String t) {
        return checkIsomorphic(s, t) && checkIsomorphic(t, s);
    }
}

Time Complexity

if n is the size of the string. Then the worst-case time complexity will be O(n).

Space Complexity

The space complexity of the isIsomorphic method is O(n), where n is the length of the input strings s and t. Because we have used a hashmap to store the mapping of the character, in the worst case it will take O(n) as the map will store n key-value pairs.

Thank you for reading the post, I hope this would have helped you to understand the question better and the solution helped you to get a clear understanding of the approach used.

Feel free to drop any comments, I would have to solve your queries and improve my solution.