Isomorphic Strings Leetcode Solution  

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Google Intel LinkedIn Microsoft Oracle Yahoo
algorithms coding HashMap Interview interviewprep LeetCode LeetCodeSolutions String

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

Isomorphic Strings Leetcode SolutionPin

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.
See also
Mean of Array After Removing Some Elements Leetcode Solution

Algorithm

  1. Initialize a character to character hashmap replacement and a character to boolean hashmap used
  2. 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
  3. 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

Complexity Analysis of Isomorphic Strings Leetcode Solution

Time Complexity

O(N), N = length of strings s and t.

Space Complexity 

O(1), as there will be a constant number of unique characters in the input.

1
Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Refresh