Isomorphic Strings Leetcode Solution

Table of Contents

Problem Statement

In this problem, we are given two strings, a and b. Our goal is to tell whether the two strings are isomorphic or not.

Two strings are called isomorphic if and only if the characters in the first string can be replaced by any character(including itself) at all points of its occurrence while keeping the relative order of the characters the same. No two characters can map to the same character.

Example

s = "abb"  , t = "cdd"

true

s = "Google" , t = "123456"

false

Approach

We can use hashmaps to save the replacement for every character in the first string. If we reach a position where there is a replacement for the first character,

We can check if the replacement is the same as the character in the other string. If not, the strings can’t be isomorphic.
In case there is no replacement for the first character, we can check if the second character has been used as the replacement for any other character in the first string. This check is important because we need to map every character in the first string to a unique character. If there exists no character whose replacement is the second character, we can assign the second character as the replacement of the first character. Otherwise, the strings are not isomorphic.

Algorithm

Initialize a character to character hashmap replacement and a character to boolean hashmap used
Iterate for every character in the string s and t:
- If replacement contains s[i] as a key:
  - If replacement[s[i]] != t[i]
    - return false
- Else:
  - If used[t[i]] == true
    - return false
  - set replacement[s[i]] = t[i]
  - set used[t[i]] = true
Return true

Implementation of Isomorphic Strings Leetcode Solution

C++ Program

#include <bits/stdc++.h>

using namespace std;

bool isIsomorphic(string s , string t) {
    int n = s.length();

    unordered_map <char , char> replacement;
    unordered_map <char , bool> used;

    for(int i = 0 ; i < n ; i++)
    {
        if(replacement.count(s[i]))
        {
            if(replacement[s[i]] != t[i])
                return false;
        }
        else
        {
            if(used[t[i]])
                return false;
            replacement[s[i]] = t[i];
            used[t[i]] = true;
        }
    }

    return true;
}

int main() {
    string s = "abb" , t = "cdd";
    cout << (isIsomorphic(s , t) ? "true" : "false") << endl;
    return 0;
}

Java Program

import java.util.*;

class isomorphic_string {
    public static void main(String args[]) {
        String s = "abb" , t = "cdd";
        System.out.println(isIsomorphic(s , t) ? "true" : "false");
    }

    public static boolean isIsomorphic(String s , String t) {
        HashMap <Character , Character> replacement = new HashMap <>();
        HashMap <Character , Boolean> used = new HashMap <>();

        for(int i = 0 ; i < s.length() ; i++) {
            if(replacement.containsKey(s.charAt(i))) {
                if(replacement.get(s.charAt(i)) != t.charAt(i))
                    return false;
            }
            else {
                if(used.containsKey(t.charAt(i)))
                    return false;
                replacement.put(s.charAt(i) , t.charAt(i));
                used.put(t.charAt(i) , true);
            }
        }

        return true;
    }
}

true