Use two arrays to make sure one-2-one mapping, O(n)


  • 0
    D

    Use the array map to save the mappings created so far and the array demap to save the reverse mapping to make sure it is a one-2-one mapping

       class Solution {
        public:
            bool isIsomorphic(string s, string t) {
                int len = s.size();
                int i;
                vector<char> map(128,0);
                vector<char> demap(128,0);
        
                for(i=0; i<len;i++)
                {
                    if(map[s[i]]) 
                    { // if s[i] is mapped to some character before
                        if(map[s[i]]!=t[i]) return false;
                    }
                    else
                    { // if s[i] never occurs before, check if some other char is mapped to t[i]
                        if(!demap[t[i]]) 
                        {   // if t[i] is available, update map and demap
                            map[s[i]] = t[i];
                            demap[t[i]] = s[i];
                        }
                        else
                        { // if t[i] is not available, return false
                            return false;
                        }
                    }
                }
                return true;
            }
    
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.