My 6 lines solution


  • 177
    G
    class Solution {
    public:
        bool isIsomorphic(string s, string t) {
            int m1[256] = {0}, m2[256] = {0}, n = s.size();
            for (int i = 0; i < n; ++i) {
                if (m1[s[i]] != m2[t[i]]) return false;
                m1[s[i]] = i + 1;
                m2[t[i]] = i + 1;
            }
            return true;
        }
    };

  • 1
    D

    +1; Good solution; There is a slight possibility of integer overflow but as long as we can iterate the strings it won't matter.


  • 8
    M

    Nice code. To prevent overflow (as commented by Debanjan) we can add some extra code:

    bool isIsomorphic(string s, string t) {
            int m1[256]={0}, m2[256]={0};
            int count = 1;
            for(int i=0; i<s.length(); i++) {
                if(m1[s[i]]!=m2[t[i]]) return false;
                if(m1[s[i]]==0) {
                    m1[s[i]]=count;
                    m2[t[i]]=count;
                    count++;
                }
            }
            return true;
        }

  • -1
    L

    the output may be wrong if the length of s & t are not same. I think this test case should be included.


  • 0
    K

    The question has assumed s & t have the same length.


  • 2

    quick question, why 256?


  • 0
    H

    Is this clear?

    "No two characters may map to the same character but a character may map to itself."

    I thought while "egg" map to "add", "egg" shall not map to "agg" because they are same charactors and only appear twice, while "eggg" has no problem map to "aggg" since even the repeatable charactors are same, there are 3 of them, not equal to 2.


  • 22
    P

    The "i + 1" made me a bit confused, then realized "+1" is to exclude 0 from valid index. Why not initialzing the array as -1, and simply keep i in the array. This also avoids the overflow issue. AC code as below:

    class Solution {
    public:
        bool isIsomorphic(string s, string t) {
            int len = s.length();
            int m1[256], m2[256];
            for (int i = 0; i < 256; i++) {
                m1[i] = m2[i] = -1;
            }
            
            for (int i = 0; i < len; i++) {
                if (m1[s[i]] != m2[t[i]]) return false;
                m1[s[i]] = m2[t[i]] = i;
            }
            return true;
        }
    };

  • 0
    R

    128 may be able to fit


  • 0
    T

    // Just a below-5-ms C solution for reference or optimization ( thx ).

    bool isIsomorphic(char* s, char* t) {

    int length = strlen(s);    
    
    int arr[128];
    int arr2[128];
    for( int j=0; j<128; j++){ 
        arr[j] = -1;
        arr2[j] = -1;
    }
    
    for( int i = 0; i<length; i++){
        if( arr[ s[i] ] == -1 && arr2[ t[i] ] == -1 ){
            arr[ s[i] ] = t[i];
            arr2[ t[i]] = s[i];
        }else if( arr[ s[i] ] != t[i] || arr2[ t[i] ] != s[i] )
            return false;
        else
            continue;
    }
    
    return true;
    

    }


  • 0
    F

    very smart ,"m1[s[i]] = i+1; m2[t[i]] = i + 1;" is a nice seeting .Because first time i use x[s[i]] +=1; y[t[i]] += 1; can't solve the char's order just like "aba" , "aab". You solution is clear and smart.


  • 3
    T

    What about space? Won't using a hash table be much more efficient space-wise, especially for short strings?


  • 0
    P
    bool isIsomorphic(char* s, char* t) {
        int i = 0, m1[256] = {0}, m2[256] = {0};
        for(i = 0; s[i] != 0 && t[i] != 0; i++){
            if(m1[s[i]] != m2[t[i]])
                return false;
            m1[s[i]] = m2[t[i]] = -i - 1;
        }
        return true;
    }
    

    No overflow problem.


  • 0
    Q

    great. mine may be less simple and elegant, but more intuitive and still simple.

    intuitively two map needed, so I use two array,
    a mapper and a reverse mapper.

    class Solution {
    public:
        bool isIsomorphic(string s, string t) {
            int mapper[256]={0}, rmapper[256]={0};
    		int i, len=s.size()==t.size()?s.size():-1; // to handle unequal length
            for(i=0;i<len;++i) {
                if(mapper[s[i]]) { if(t[i]!=mapper[s[i]]) return false; } // s[i] already mapped
                else {
                    if(!rmapper[t[i]]) { mapper[s[i]]=t[i]; rmapper[t[i]]=s[i]; } // t[i] not mapped yet
                    else if(s[i]!=rmapper[t[i]]) return false; // t[i] already mapped
                }
            }
            return len!=-1;
        }
    };

  • 0

    Hi, TMS. Well, both will be O(1) space but it would be faster to handle arrays.


  • 0

    Well, initializing to 0 will enable the arrays to be initialized collectively and thus saves code :-)


  • 1

    Well, the code can be simplified much.

    1. Initializing to 0 will enable collective initialization and save code;
    2. For C-style char*, there is no need to compute strlen(s) because s[i] will just tell us whether this is the end of the string \0.

    The code is as follows: 5 lines and 0 ms.

    bool isIsomorphic(char* s, char* t) {
        int sp[256] = {0}, tp[256] = {0};
        for (int i = 0; s[i]; i++) {
            if (sp[s[i]] != tp[t[i]]) return false; 
            sp[s[i]] = tp[t[i]] = i + 1;
        }
        return true;
    }

  • 0
    G

    Why this can avoid overflow issue?


  • 1
    K

    what if t is longer than s?


  • 0
    T

    @jianchao.li.fighter, that's true, it would be faster to handle arrays. Both will be constant space, correct but my point is that in several cases, 256 characters will not be used and so this could be considered a waste of space. But then 256 spaces of memory isn't much, so no big deal I guess.


Log in to reply
 

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