Java 中的同构字符串

这是许多顶尖 IT 公司（如Google、Amazon、TCS、Accenture、Uber等）经常询问的一个非常有趣的问题。通过解决这个问题，可以考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将讨论什么是同构字符串以及如何判断字符串是否同构，并提供不同的方法和逻辑。我们还将创建相应的 Java 程序。

同构字符串

如果一个字符串的字母可以映射到另一个字符串，则称这两个字符串为同构。映射意味着用另一个字母替换一个字母的所有出现，但字母的顺序保持不变。请注意，没有两个字母可以映射到同一个字母，但一个字母可以映射到自身。

让我们通过示例来理解。

示例 1

假设 string1 是 ABACB，string2 是 XPZ。现在将 string1 映射到 string2。

将 A -> X，B -> P，A -> X，C -> Z，B -> P。

因此，我们观察到 string1 和 string2 彼此同构。

让我们看另一个例子。

示例 2

假设 string1 是 PQPRQP，string2 是 XPZW。现在将 string1 映射到 string2。

将 P -> T，Q -> U，P -> T，R -> V，Q -> U，P -> W。

因此，我们观察到 string1 和 string2不是同构的。

算法

1. 考虑一个映射表，该表将第一个字符串中的每个字符映射到第二个字符串中的一个且仅一个字符。
2. 再考虑一个表，称为 mappedBefore 表。它记录第二个字符串中已与第一个字符串中的某个字符相关联的每个字符。
3. 逐个读取第一个字符串的字符。
4. 如果字符存在于映射表中，则获取其映射。
5. 读取第二个字符串中的相应字符。
6. 如果映射和从第二个字符串读取的字符不相同，则返回 false。
7. 否则，检查第一个字符串中读取的字符是否不存在于映射表中，然后执行以下操作：
   1. 读取第二个字符串中的相应字符。
   2. 如果字符存在于 mappedBefore 表中，则返回 false。
   3. 否则，将第一个字符串和第二个字符串中的字符添加到映射表中。
8. 转到步骤 3 并继续。
9. 返回 true。

让我们在 Java 程序中实现上述算法。

Java 程序：检查两个字符串是否同构

IsomorphicString.java

输出

Are KITE and ZXBN Isomorphic? true