問題描述

給定兩個字符串s和t，判斷它們是否同構，是則返回true，否則返回false。

按照如下替換規則，如果字符串t能夠通過替換字符串s中所有字符得到，則字符串s和字符串t同構。

替換時，必須保證字符串中各字符的出現順序不變；

替換時，所有相同的字符只能被一個唯一字符替換；

替換時，不同的字符不能被同一個字符替換；

替換時，一個字符可以被它本身所替換。

注意：假定字符串s與字符串t長度相同。

?

輸入示例

input1	input2	input3
"egg"	"foo"	"paper"
"add"	"bar"	"title"

　　

?

?

?

輸出示例

output1	output2	output3
true	false	true

?

　

?

---

算法實現

注意到這里只是針對字符，所以利用ASCII碼的關系在對應的字符的數位上存儲該字符在字符串中上一次出現的位置。

判斷字符串s與字符串t在對應下標位置i上的字符在該字符串中上次出現的位置是否相同。

如果不同，則說明字符串s與字符串t不同構，返回false。

如果相同，至少說明字符串s的子字符串s.substring(0, i)與字符串t的子字符串t.substring(0, i)同構，應該繼續判斷字符串s與字符串t在對應下個位置上的字符在該字符串中上次出現的位置是否相同，直至到最后一個字符。如果最后一個字符的判斷結果仍然相同，則說明字符串s與字符串t同構，返回true。

1 public class Solution { 2 public boolean isIsomorphic(String s, String t) { 3 int[] m = new int[256]; 4 for(int i=0; i<s.length(); i++){ 5 if(m[s.charAt(i)] != m[t.charAt(i)+128]) return false; 6 m[s.charAt(i)] = m[t.charAt(i)+128] = i+1; 7 } 8 return true; 9 } 10 }

轉載于:https://www.cnblogs.com/shenxiaolong/p/6790311.html

總結

以上是生活随笔為你收集整理的Isomorphic Strings的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。