同構字符串
-
給定兩個字符串 s 和 t ，判斷它們是否是同構的。
-
如果 s 中的字符可以按某種映射關系替換得到 t ，那么這兩個字符串是同構的。
-
每個出現的字符都應當映射到另一個字符，同時不改變字符的順序。不同字符不能映射到同一個字符上，相同字符只能映射到同一個字符上，字符可以映射到自己本身。
示例 1:
輸入：s = “egg”, t = “add”
輸出：true
解題思路
- 可以使用兩個哈希表來解決這個問題。遍歷字符串 s 和 t， 分別維護兩個哈希表來記錄字符之間的映射關系。
- 如果遇到一個新的字符，則將其映射到另一個新的字符上，并將映射關系存儲在哈希表中；
- 如果遇到已存在的字符，則檢查其映射關系是否與另一個字符串相符，如果不符則返回 false。
- 如果遍歷完成后未出現問題，則返回 true。
Java實現
public class IsomorphicStrings {public boolean isIsomorphic(String s, String t) {if (s.length() != t.length()) {return false;}Map<Character, Character> sMap = new HashMap<>();Map<Character, Character> tMap = new HashMap<>();for (int i = 0; i < s.length(); i++) {char sCh = s.charAt(i);char tCh = t.charAt(i);//s映射t要一一對應if (!sMap.containsKey(sCh)) {sMap.put(sCh, tCh);} else if (sMap.get(sCh) != tCh) {return false;}//t映射s也要一一對應if (!tMap.containsKey(tCh)) {tMap.put(tCh, sCh);} else if (tMap.get(tCh) != sCh) {return false;}}return true;}public static void main(String[] args) {IsomorphicStrings isomorphicStrings = new IsomorphicStrings();String s1 = "badc", t1 = "baba";System.out.println("Test Case 1:");System.out.println("s: \"egg\", t: \"add\"");System.out.println("Result: " + isomorphicStrings.isIsomorphic(s1, t1)); // Expected: trueString s2 = "foo", t2 = "bar";System.out.println("\nTest Case 2:");System.out.println("s: \"foo\", t: \"bar\"");System.out.println("Result: " + isomorphicStrings.isIsomorphic(s2, t2)); // Expected: falseString s3 = "paper", t3 = "title";System.out.println("\nTest Case 3:");System.out.println("s: \"paper\", t: \"title\"");System.out.println("Result: " + isomorphicStrings.isIsomorphic(s3, t3)); // Expected: true}
}時間空間復雜度
-
時間復雜度： 遍歷字符串 s 和 t，時間復雜度為 O(n)，其中 n 是字符串的長度。
-
空間復雜度： 使用了兩個哈希表來存儲映射關系，空間復雜度為O(n)，其中 n 是字符串的長度。
)
