LEET code -- Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

用兩個table分別記錄  什麼時候哪個字在哪邊出現
如果出現紀錄不一樣  就直接回傳錯誤

但是下面這版本 超級慢304ms

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

struct Node{ char str[1]; int index; struct Node*next; }; bool isIsomorphic(char* s, char* t) { int size=256; struct Node ** tableS=calloc(size,sizeof(struct Node *)); struct Node ** tableT=calloc(size,sizeof(struct Node *)); int state=0; for(int i=0;s[i];i++){ //printf("\nprocess %c,%c:\n",s[i],t[i]); state=0; for(int j=0;j<size;j++){ if(tableS[j]==NULL){ tableS[j]=malloc(sizeof(struct Node)); tableS[j]->str[0]=s[i]; tableS[j]->index=i; tableS[j]->next=NULL; state+=1; //printf("%d S null,",state); // break; }else if(tableS[j]->str[0]==s[i]){ //printf("%d S i,",state); struct Node *temp=tableS[j]; while((temp->next!=NULL)){//can't use !(temp->next) temp=temp->next; } temp->next=malloc(sizeof(struct Node)); temp->next->str[0]=s[i]; temp->next->index=i; temp->next->next=NULL; state+=100; //printf("%d S incr,",state); } if(tableT[j]==NULL){ tableT[j]=malloc(sizeof(struct Node)); tableT[j]->str[0]=t[i]; tableT[j]->index=i; tableT[j]->next=NULL; state+=1; //printf("%d T null,",state); // break; }else if(tableT[j]->str[0]==t[i]){ struct Node *temp=tableT[j]; while((temp->next!=NULL)){ temp=temp->next; } temp->next=malloc(sizeof(struct Node)); temp->next->str[0]=t[i]; temp->next->index=i; temp->next->next=NULL; state+=100; //printf("%d T incr,",state); } if(state==1 || (state >2 && state<200 )|| state>=201)return false; else if(state==2 || state==200)break; } } return true; }

------------
把重複出現的 移除  減少迴圈
204ms還是慢

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

struct Node{ char str[1]; int index; struct Node*next; }; bool isIsomorphic(char* s, char* t) { int size=256; struct Node ** tableS=calloc(size,sizeof(struct Node *)); struct Node ** tableT=calloc(size,sizeof(struct Node *)); int state=0; for(int i=0;s[i];i++){ //printf("\nprocess %c,%c:\n",s[i],t[i]); state=0; for(int j=0;j<size;j++){ int counterS=0,counterT=0; if(tableS[j]==NULL && tableT[j]==NULL){ tableS[j]=malloc(sizeof(struct Node)); tableS[j]->str[0]=s[i]; tableS[j]->index=i; tableS[j]->next=NULL; state+=1; //printf("%d S null,",state); // break; tableT[j]=malloc(sizeof(struct Node)); tableT[j]->str[0]=t[i]; tableT[j]->index=i; tableT[j]->next=NULL; state+=1; }else if(tableS[j]->str[0]==s[i] && tableT[j]->str[0]==t[i]){ //printf("%d S i,",state); struct Node *tempS=tableS[j]; struct Node *tempT=tableT[j]; while((tempS->next!=NULL && tempT->next!=NULL)){//can't use !(temp->next) tempS=tempS->next; tempT=tempT->next; //counterS++; } if(tempT->next!=NULL || tempS->next!=NULL)return false;//if is not a same location tempS->next=malloc(sizeof(struct Node)); tempS->next->str[0]=s[i]; tempS->next->index=i; tempS->next->next=NULL; state+=100; //printf("%d S incr,",state); tempT->next=malloc(sizeof(struct Node)); tempT->next->str[0]=t[i]; tempT->next->index=i; tempT->next->next=NULL; state+=100; }else if(tableS[j]->str[0]==s[i] || tableT[j]->str[0]==t[i]){ //if is not a same location return false; } if(state==1 || (state >2 && state<200 )|| state>=201)return false; else if(state==2 || state==200)break; } } return true; }

------
突然發覺  我幹嘛記錄所有重複字串的位置
知道他上一次位置就好
因為 如果 S T不一樣  index就不一樣

24ms 還是不夠快

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

struct Node{ char str[1]; int index; struct Node*next; }; bool isIsomorphic(char* s, char* t) { int size=256; int tableS[size]; int tableT[size]; char a=' '; memset(tableS,-1,size*sizeof(int));//need sizeof memset(tableT,-1,size*sizeof(int)); for(int i=0;s[i];i++){ //printf("\nprocess %c,%c:\n",s[i],t[i]); //printf("%d: %d %d\n",(int)s[i] - (int)a,tableS[ (int)s[i] - (int)a ],tableT[ (int)t[i] - (int)a]); if(tableS[ (int)s[i] - (int)a ] != tableT[ (int)t[i] - (int)a])return false; tableS[ (int)s[i] - (int)a ]=i; tableT[ (int)t[i] - (int)a ]=i; } return true; }