同构字符串
-
给定两个字符串 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 是字符串的长度。
)
