這是悅樂書的第191次更新猖辫，第194篇原創(chuàng)
01 看題和準(zhǔn)備
今天介紹的是LeetCode算法題中Easy級(jí)別的第50題（順位題號(hào)是205）测暗。給定兩個(gè)字符串s和t钧萍，確定它們是否是同構(gòu)的窄俏。如果s中的字符可以替換為t，則兩個(gè)字符串是同構(gòu)的城须。
所有出現(xiàn)的字符必須替換為另一個(gè)字符蚤认，同時(shí)保留字符的順序。 沒有兩個(gè)字符可以映射到相同的字符糕伐，但字符可以映射到自身砰琢。例如：
輸入：s =“egg”，t =“add”
輸出：true
輸入：s =“foo”，t =“bar”
輸出：false
輸入：s =“paper”氯析，t =“title”
輸出：true
注意：可以假設(shè)s和t都具有相同的長度亏较。
本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8掩缓，環(huán)境是win7 64位系統(tǒng)雪情，使用Java語言編寫和測(cè)試。
02 第一種解法
因?yàn)轭}目已經(jīng)假設(shè)兩個(gè)字符串的長度是相等的你辣，所以不用考慮特殊情況巡通。
使用兩個(gè)HashMap，分別存儲(chǔ)字符串s和字符串t的每一位字符舍哄，再使用兩個(gè)新的字符串str和str2宴凉，分別存儲(chǔ)其對(duì)應(yīng)字符的結(jié)構(gòu)，如果字符已經(jīng)存在表悬，則取出之前存的下標(biāo)添加到str或str2中弥锄，如果是新出現(xiàn)，就把當(dāng)前的下標(biāo)添加到str或str2中蟆沫。最后得到的str和str2就是s籽暇、t所表示的結(jié)構(gòu)，如果str和str2相等饭庞，則返回true戒悠，否則返回false。
public boolean isIsomorphic(String s, String t) {
Map<Character, Integer> map = new HashMap<>();
String str = "";
for (int i=0; i<s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
str = str + map.get(s.charAt(i));
} else {
map.put(s.charAt(i), i);
str += i;
}
}
Map<Character, Integer> map2 = new HashMap<>();
String str2 = "";
for (int j=0; j<t.length(); j++) {
if (map2.containsKey(t.charAt(j))) {
str2 = str2 + map2.get(t.charAt(j));
} else {
map2.put(t.charAt(j), j);
str2 += j;
}
}
return str.equals(str2);
}
時(shí)間復(fù)雜度：因?yàn)閒or循環(huán)中使用了HashMap的containsKey方法舟山，而此方法最好的情況就是要判斷的key正好是第一位绸狐，則containsKey方法的時(shí)間復(fù)雜度是O(1)，最壞的情況是要判斷的key在最后一位累盗，則containsKey方法的時(shí)間復(fù)雜度是O(n)寒矿。因此，此解法的時(shí)間復(fù)雜度最好情況是O(n)若债，最壞情況是O(n^2)劫窒。
空間復(fù)雜度：O(n)
03 第二種解法
依舊使用兩個(gè)HashMap，同樣是將兩個(gè)字符串的各個(gè)字符放入map中拆座，不過由第一種解法的分開放變成同時(shí)放，如果在進(jìn)行put的時(shí)候冠息，有兩種情況：當(dāng)前字符在map中不存在的時(shí)候挪凑，返回null；當(dāng)前字符在map中存在的時(shí)候逛艰，返回此字符作為key所關(guān)聯(lián)的之前的value躏碳。如果兩邊的字符進(jìn)行put操作而不相等，即說明此字符在兩個(gè)map中的其中一個(gè)已經(jīng)出現(xiàn)過一次散怖，但是另外一個(gè)沒出現(xiàn)過菇绵，也就表示兩字符串的結(jié)構(gòu)是不同的肄渗。
public boolean isIsomorphic2(String s, String t) {
Map<Character, Integer> map = new HashMap<>();
Map<Character, Integer> map2 = new HashMap<>();
for (Integer i=0; i<s.length(); i++) {
if (map.put(s.charAt(i), i) != map2.put(t.charAt(i), i)) {
return false;
}
}
return true;
}
04 第三種解法
只使用一個(gè)HashMap。思路與上面兩種解法類似咬最，不過是將字符串s的各個(gè)字符當(dāng)成了map的key翎嫡，將字符串t的各個(gè)字符當(dāng)成map的value。只要map中存在當(dāng)前的字符key永乌，那么其所對(duì)應(yīng)的value應(yīng)該和另外一個(gè)字符串的當(dāng)前字符相等惑申，否則就是結(jié)構(gòu)不同。
public boolean isIsomorphic3(String s, String t) {
HashMap<Character, Character> map = new HashMap<>();
int size = s.length();
for (int i = 0; i < size; i++) {
if (map.containsKey(s.charAt(i))) {
if (t.charAt(i) != map.get(s.charAt(i))) {
return false;
}
} else {
if (map.containsValue(t.charAt(i))) {
return false;
}
map.put(s.charAt(i), t.charAt(i));
}
}
return true;
}
05 第四種解法
對(duì)于上面的解法使用HashMap來存字符翅雏，我們可以只用數(shù)組來替代圈驼，因?yàn)榻M成字符串的字符類型有限，ASCII碼只有256個(gè)字符,所以我們預(yù)先定義好兩個(gè)大小為256的整型數(shù)組望几，創(chuàng)建后兩數(shù)組中的元素初始值都是0绩脆。此時(shí)，我們使用for循環(huán)對(duì)字符串s進(jìn)行遍歷橄抹，當(dāng)前字符所表示的十進(jìn)制值當(dāng)做是數(shù)組的索引靴迫，如果該索引分別對(duì)應(yīng)的值不相等，則說明兩字符串不是同結(jié)構(gòu)害碾，否則矢劲，就將循環(huán)內(nèi)的指針i作為其索引對(duì)應(yīng)的值。其中i是從0開始的慌随，但是數(shù)組初始化后其內(nèi)所有元素都是默認(rèn)值0芬沉，所以需要加1來區(qū)別默認(rèn)值0。
public boolean isIsomorphic4(String s, String t) {
int[] m1 = new int[256];
int[] m2 = new int[256];
for (int i = 0; i < s.length(); i++) {
if (m1[s.charAt(i)] != m2[t.charAt(i)]) return false;
m1[s.charAt(i)] = i + 1;
m2[t.charAt(i)] = i + 1;
}
return true;
}
此解法時(shí)間復(fù)雜度是O(n)阁猜，空間復(fù)雜度是O(1)丸逸。
06 小結(jié)
算法專題目前已連續(xù)日更超過一個(gè)月，算法題文章50+篇剃袍，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】黄刚、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞民效，獲取系列文章合集憔维。
以上就是全部內(nèi)容，如果大家有什么好的解法思路畏邢、建議或者其他問題业扒，可以下方留言交流，點(diǎn)贊舒萎、留言程储、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持！
