Accepted C Solution Rt O(n) Sp O(1) with some explanation


  • 0
    R
    bool isIsomorphic(char* s, char* t) {
    	int ms[255]={0};
    	int mt[255]={0};
    	char *ps=s;
    	char *pt=t;
    	while(0!=*ps){
    		int i = *ps;
    		int j = *pt;
    		if(0!=ms[i]){
    			if(ms[i]!=j)
    				return false;
    		} else {
    			if(0!=mt[j])
    				return false;
    			ms[i]=j;
    			mt[j]=i;
    		}
    
    		++pt;
    		++ps;
    	}
    	return true;
    }
    

    the range of type char is 0~255, and 0 is the terminal NULL which will never be mapped.just store the mapped indexes between s and t.


  • 0
    R

    the space needed could be reduced in theory, by studying the character set can be printed.like the function isprint in ctype.h http://www.cplusplus.com/reference/cctype/
    which indicate that 127 will be enough


Log in to reply
 

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