No result illustrationNo result illustration

DevLoom

search

Lets Connect

chevron right
Menu
Home

Home

Community

Community

Blog Posts

Blog Posts

Programming

Programming

Tech Topics

Tech Topics

Explore

Explore

Find Jobs

Find Jobs

Tags

Tags

DevLoomPerfect Place for devs
    profile

    Jubair

    upvoteupvote

    1

    downvote

    0

    star

    Isomorphic Strings using C++

    clock icon

    Asked 11 months 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/

    Strings
    Hashing
    LeetCode
    easy

    Share

    Write your comment here !

    0 Responses