Isomorphic Strings using C++

clock icon

Asked 1 year ago

message

0Comments

eye

1 Views

Imagine we're playing a secret code game with words!

Let's say we have two words: "EGG" and "ADD"

We want to know if we can turn "EGG" into "ADD" by replacing letters, but we have to follow some special rules:

  1. Each letter in "EGG" must change to the same letter in "ADD" every time it appears.
  2. Two different letters in "EGG" can't change into the same letter in "ADD".
  3. We can't change the order of the letters.
E -> A
G -> D

EGG -> ADD

Let's try it: 

P -> T
A -> I
P -> T (already done)
E -> L
R -> E

PAPER -> TITLE

But what about "FOO" and "BAR"?

F -> B
O -> A
O -> ?

Uh oh! We have a problem. We already used 'A' for the second letter, so we can't use it again for the third letter. There's no way to make this work, so......

"FOO" and "BAR" are not isomorphic.

The trick is to make sure that:

  1. Each letter always changes to the same new letter.
  2. We never use the same new letter for two different original letters
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int hash[256] = {0} ;

        bool isSecondCharsMapped[256] = {0}; 
         //  stores if t[i] is mapped wiht s[i] 
        // also checks if mapping already happend or not 

        for(int i =0 ;  i< s.size() ; i++){
            if(hash[s[i]]==0  && isSecondCharsMapped[t[i]] == 0 ){
                // then Map 
                hash[s[i]] = t[i] ;
                isSecondCharsMapped[t[i]] = true ;
            }
        }

        for(int i= 0 ; i<s.size() ; i++){
                if(hash[s[i]] != t[i]){
                 return false ;
            }
        }
        return true ;
        
    }
};

The clever part of your solution is:

  • Using the hash box to remember what each letter should change into.
  • Using the isSecondCharsMapped box to make sure we don't use the same disguise twice.
  • Checking twice: once to set up the code, and once to make sure it works for the whole word.

Feel free to checkout one more problem with similar approch ! 

https://leetcode.com/problems/valid-anagram/description/

Share

Write your comment here !

0 Responses