My solution but slow


  • 0
    V
    class Solution {
    public:
        bool isIsomorphic(string s, string t) {
            unordered_map<char, char> index;
            unordered_map<char, bool> tag;
    
            for( int i = 0; i < s.size(); i++ )
            {
                if( !index[ s[ i ] ] )
                {
                    if( !tag[ t[ i ] ] )    // if not appeared before
                    {
                        index[ s[ i ] ] = t[ i ];
                        tag[ t[ i ] ] = true;
                    }
                    else    // many to one
                        return false;
                }
    
                else if( index[ s[ i ] ] != t[ i ] )    // have appeared but illegal
                    return false;
            }
            return true;
        }
    };

  • 0
    L

    Replace the map by array to increase the performance.

    Solution 8ms - O(n) (JAVA)

    public class Solution {
        public boolean isIsomorphic(String s, String t) {
            if(s.length() != t.length()) return false;
    
            int N = s.length();
            int[] mst = new int[256];
            int[] mts = new int[256];
            
            for(int i = 0; i < N; i++) {
                char cs = s.charAt(i);
                char ct = t.charAt(i);
                
                if((mst[cs] == 0) && (mts[ct] == 0)) {
                    mst[cs] = ct;
                    mts[ct] = cs;
                }
                
                if((mst[cs] != ct) || (mts[ct] != cs)) 
                    return false;
            }
            
            return true;
        }
    }

Log in to reply
 

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