同构字符串指的是两个字符串s和t，它们满足字符之间存在一一对应的映射关系，即s中的每个字符都唯一对应t中的一个字符，且t中的每个字符也唯一对应s中的一个字符，映射关系不能出现多对一或者一对多的情况。比如"egg"和"add"就是同构字符串，e对应a，g对应d；而"foo"和"bar"不是同构字符串，因为o同时对应a和r，违反了映射规则。
传统实现方式的不足
常见的同构字符串判断思路是使用两个哈希表分别记录s到t和t到s的映射关系，遍历字符串时不断校验映射是否冲突。这种方式需要维护两个映射结构，逻辑相对繁琐，而且哈希表的增删操作也会带来一定的性能开销。当字符串长度较长时，这种实现的效率优势并不明显。
基于字符位置模式的实现原理
基于字符位置模式的思路核心在于：如果两个字符串是同构的，那么对于任意下标i，s中字符s[i]首次出现的位置，一定和t中字符t[i]首次出现的位置相同。我们只需要记录每个字符在字符串中第一次出现的下标，然后对比两个字符串对应位置的首次出现下标是否一致即可，不需要维护复杂的映射关系。
具体实现步骤如下：
- 首先判断两个字符串的长度是否相等，如果不相等直接返回false，因为长度不同的字符串不可能是同构的
- 创建两个长度为256的数组，分别用来记录s和t中每个字符首次出现的下标，数组初始化为-1，表示字符还未出现过
- 遍历两个字符串的每个字符，获取当前字符在对应数组中的首次出现位置
- 如果两个首次出现位置不相等，说明字符的映射模式不一致，返回false
- 如果首次出现位置是-1，说明字符是第一次出现，将当前下标记录到对应的数组中
- 遍历结束后没有返回false，说明两个字符串是同构的，返回true
完整Java代码实现
以下是基于字符位置模式的同构字符串判断的完整Java代码：
public class IsomorphicStrings {
public boolean isIsomorphic(String s, String t) {
// 长度不同直接返回false
if (s.length() != t.length()) {
return false;
}
// 记录s中每个字符首次出现的下标，初始化为-1
int[] sIndex = new int[256];
// 记录t中每个字符首次出现的下标，初始化为-1
int[] tIndex = new int[256];
for (int i = 0; i < sIndex.length; i++) {
sIndex[i] = -1;
tIndex[i] = -1;
}
// 遍历字符串的每个字符
for (int i = 0; i < s.length(); i++) {
char sChar = s.charAt(i);
char tChar = t.charAt(i);
// 获取两个字符的首次出现位置
int sFirst = sIndex[sChar];
int tFirst = tIndex[tChar];
// 首次出现位置不一致，返回false
if (sFirst != tFirst) {
return false;
}
// 如果是第一次出现，记录当前下标
if (sFirst == -1) {
sIndex[sChar] = i;
tIndex[tChar] = i;
}
}
return true;
}
// 测试方法
public static void main(String[] args) {
IsomorphicStrings solution = new IsomorphicStrings();
// 测试用例1：同构字符串
System.out.println(solution.isIsomorphic("egg", "add")); // 输出true
// 测试用例2：非同构字符串
System.out.println(solution.isIsomorphic("foo", "bar")); // 输出false
// 测试用例3：长度不同
System.out.println(solution.isIsomorphic("ab", "abc")); // 输出false
// 测试用例4：单字符字符串
System.out.println(solution.isIsomorphic("a", "b")); // 输出true
}
}
复杂度分析
这种实现方式的时间复杂度和空间复杂度都很优秀：
- 时间复杂度：只需要遍历一次字符串，数组的初始化操作是固定长度的256次，整体时间复杂度为O(n)，n是字符串的长度
- 空间复杂度：使用了两个固定长度为256的数组，空间复杂度为O(1)，不会随着字符串长度的增加而增长
注意事项
在实际使用中需要注意几个问题：
- 字符集范围：上述代码假设字符串中的字符是ASCII字符，所以数组长度设为256，如果字符串包含Unicode字符，可以将数组替换为
HashMap<Character, Integer>来存储首次出现位置，逻辑和数组实现一致 - 空字符串处理：如果两个字符串都是空字符串，按照同构的定义应该返回true，上述代码可以正确处理这种情况，因为长度相同且遍历不会执行，直接返回true
- 大小写敏感：上述代码是大小写敏感的，比如"A"和"a"会被认为是不同的字符，如果需要忽略大小写，可以在遍历前将字符串统一转为小写或者大写
基于字符位置模式的实现方式逻辑简洁，性能高效，相比传统的双哈希表实现减少了映射维护的开销，是判断同构字符串的优选方案。