205. Isomorphic Strings(同構(gòu)字符串)

對于同構(gòu)字符串來說也就是對于字符串s與字符串t，對于$s[i]$可以映射到$t[i]$,同時對于任意$s[k]=s[i]$都有$s[k]$映射到$t[k]$,則$t[k]=t[i]$則說明這是一個同構(gòu)字符串。
我們已經(jīng)明白了映射規(guī)則，接下來我們就具體來分析下如何判斷是否為同構(gòu)字符串。
在ASCII碼對照表中一共有128個字符，也就是說對于題目給出的字符串我們可以確定它們是這128個字符中的字符組成的，每個字符都有兩種表示一種是ASCII碼，一種是字符本身。
我們就可以創(chuàng)建一個大小為128的char類型數(shù)組f，用ASCII碼$x$作為下標(biāo)，表示s中所有ASCII碼為$x$的元素$f[x]$映射為t中的對應(yīng)位置的元素。
映射如圖所示：

之后每一次添加映射都要對應(yīng)的映射f[s[i]]是否已經(jīng)存在，如果存在是否與當(dāng)前要添加的映射是否相同，如果相同則沒事，不相同就說明存在一個映射到多個元素，那就不符合同構(gòu)字符串的定義了。
之后我們還需要檢查一下是否存在多個元素映射到同一個元素的情況存在，因為上述添加的過程在建立映射后只能保證不存在一個映射到多個的情形，但是沒法避免多個元素到一個元素的情形，所以我們需要進行額外的檢查。

總結(jié)

根據(jù)字符的兩種表現(xiàn)形式我們可以建立數(shù)組描述映射。我們可以發(fā)現(xiàn)在遍歷字符串s與t，將對應(yīng)位置的元素映射關(guān)系逐一加入到f數(shù)組中，在加入的過程中如果發(fā)現(xiàn)映射已存在，但是映射的元素不相同，說明這兩個不是同構(gòu)字符串，我們返回false，一直到結(jié)束，如果s中所有元素都與t中對應(yīng)位置的元素建立了映射，則我們需要檢查是否存在多個s中的不同字符映射到了t中的同一個字符上，如果存在返回false，否則返回true。
至此程序結(jié)束。

bool isIsomorphic(char* s, char* t) {int length1 = strlen(s);int length2 = strlen(t);char * f = (char *)malloc(sizeof(char)*128);for(int i = 0; i < 128; i++){f[i] = 0;}if(length1==length2){for(int i = 0; i < length1; i++){if(f[s[i]]==0){f[s[i]] = t[i];}else if(f[s[i]]!=t[i]){return 0;}}for(int i = 0; i < 128; i++){for(int j = 0; j < i; j++){if(f[i]==f[j]&&f[i]!=0){return 0;}}}return 1;}return 0;
}

運行結(jié)果截圖：