Isomorphic String template C++
vishal
161

Isomorphic String For Practice

Sharing Isomorphic string problems and sample solutions to observe on how to approach.

Identify if problems talks about similar string .

https://leetcode.com/problems/isomorphic-strings/
https://leetcode.com/problems/find-and-replace-pattern/
https://leetcode.com/problems/word-pattern/

All the above problems can be solved by Isomorphic string template with minor tweaks.
Below is a standard code for isomorphic string problems.

1.https://leetcode.com/problems/isomorphic-strings/

bool isIsomorphic(string s, string t) 
    {
       unordered_map<char,char> m;  // to connect each character of string s and t
        
       if(s.length()!=t.length())  // if length is different then it is not possible for string to be similar or isomorphic.
           return false;
        
       set<char> st;  // to store string t
        
       for(int i=0;i<s.length();i++)
       {
           if(m.find(s[i])!=m.end())  // if char of string s if map with some character of string t
           {
               if(m[s[i]]!=t[i])  // but not equals to the corresponding character of string t then return false
               {
                   return false;
               }
               
           }
           
           else    // if character of string s is not mapped
               {
                    if(st.count(t[i])>0)  // but corresponding character of string t is mapped with someone the return false
                    {
                        return false;
                    }
               
                    else  // if character of s is not mapped and corresponding character of t is also not mapped
                    {  
                        m[s[i]]=t[i];  // then mapped each other
                        st.insert(t[i]);
                        
                    }
               }
       }
        
        return true;
    }

2. https://leetcode.com/problems/find-and-replace-pattern/

 bool help(string s,string t)
    {
        if(s.length()!=t.length())
            return false;
        
        unordered_map<char,char> m;
        set<char> y;
        
        for(int i=0;i<s.length();i++)
        {
            char p=s[i];
            if(m.find(p)!=m.end())
            {
                if(m[p]!=t[i])
                    return false;
            }
            else
            {
                if(y.count(t[i])>0)
                    return false;
                else
                {
                    m[p]=t[i];
                    y.insert(t[i]);
                }
            }
        }
        
        return true;
    }
    
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) 
    {
        vector<string> v;
        for(auto w:words)
        {
           if(help(w,pattern))
               v.push_back(w);
        }
        return v;
    }

3. https://leetcode.com/problems/word-pattern/

bool wordPattern(string pattern, string s) 
    {
        unordered_map<char,string> m;
        stringstream ss(s);
        vector<string> v;
        string w;
        while(ss>>w)
        {
            v.push_back(w);
        }
        
        
        if(pattern.size()!=v.size())
            return false;
        
        set<string> y;
        
        for(int i=0;i<pattern.length();i++)
        {
            char p=pattern[i];
            if(m.find(p)!=m.end())
            {
                if(m[p]!=v[i])
                return false;
            }
            
            else
            {
               if(y.count(v[i])>0)
               {
                   return false;
               }
                
                else
                {
                   m[p]=v[i];
                   y.insert(v[i]);
                    
                }
            }
        }
        
        return true;
    }

Please correct the approach/solution if you find anything wrong.
And if you like my post then give a thumbs up : ) happy coding .

Comments (0)