LeetCode同构字符串问题：现有Java代码部分测试失败求调试帮助

题目回顾 #

给定两个字符串s和t，判断它们是否是同构的。满足以下条件则两字符串同构：

• s中的字符可以通过替换得到t
• 所有字符的出现都需替换为另一字符、保持顺序
• 不同字符不能映射到同一字符（字符可映射到自身）

示例：

• 输入s="egg"，t="add"，输出true
• 输入s="foo"，t="bar"，输出false
• 输入s="paper"，t="title"，输出true

约束条件：

• 1 ≤ s.length ≤ 5*10^4
• t.length == s.length
• s和t由合法ASCII字符组成

问题描述 #

现有Java代码大部分测试用例可通过，但在输入s="foo"、t="bar"时失败：代码返回的计数均为0，但预期s的计数应为1，t的计数为0，导致错误返回true，而正确输出应为false。

现有代码 #

import java.nio.charset.*;

class Solution {

    public static boolean isIsomorphic(String s, String t) {
        s = s.toLowerCase();
        t = t.toLowerCase();
        int matchCount1 = 0;
        int matchCount2 = 0;
        matchCount1 = checkMatching(s);
        matchCount2 = checkMatching(t);
        System.out.print(matchCount1);
        System.out.print(matchCount2);
        return matchCount1 == matchCount2;
    }

    public static int checkMatching(String s) {
        int count = 0;
        int j = 0;
        for (int i = 0; i < s.length(); i++) { // s.length == 4
            char current = s.charAt(i); // current = 'p'
            j += 1;
            while (j < s.length() - 1) {
                if (current == s.charAt(j)) { // if p != a
                    count += 1;
                    break;
                } else {
                    j++; // j == 2
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String s = "paper";
        String t = "title";

        isIsomorphic(s, t);
    }
}

代码错误分析 #

你的checkMatching函数逻辑存在根本性问题：

1. j的初始化与更新逻辑混乱：每次循环i时j +=1，导致j会快速超出字符串范围，无法正确遍历后续字符。比如处理"foo"时，i=1（字符'o'）时j已经变成3，直接跳过循环，完全没统计到第二个'o'的重复。
2. 统计逻辑无法反映同构本质：即使修复遍历问题，单纯统计重复字符次数的方式也无法区分同构所需的映射关系——比如"aab"和"abb"的重复次数相同，但它们的字符映射模式完全不同，实际并不同构。

正确解决方案 #

同构字符串的核心是双向唯一映射：每个s的字符只能映射到一个t的字符，每个t的字符也只能被一个s的字符映射。以下两种方案都能满足要求：

方案1：双向数组映射（高效版） #

利用ASCII字符范围固定的特性，用数组替代哈希表，时间复杂度O(n)，空间复杂度O(1)：

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        // 存储s到t的映射
        char[] sToT = new char[256];
        // 存储t到s的映射
        char[] tToS = new char[256];
        
        for (int i = 0; i < s.length(); i++) {
            char sc = s.charAt(i);
            char tc = t.charAt(i);
            
            // 检查s字符的映射是否冲突
            if (sToT[sc] != 0 && sToT[sc] != tc) {
                return false;
            }
            // 检查t字符的映射是否冲突
            if (tToS[tc] != 0 && tToS[tc] != sc) {
                return false;
            }
            // 建立双向映射
            sToT[sc] = tc;
            tToS[tc] = sc;
        }
        return true;
    }
}

方案2：转换为模式序列（直观版） #

将每个字符串转换为基于字符首次出现位置的模式序列，比如"foo"转换为"0,1,1,"，"bar"转换为"0,1,2,"，比较序列是否一致：

import java.util.HashMap;

class Solution {
    public boolean isIsomorphic(String s, String t) {
        return getPattern(s).equals(getPattern(t));
    }
    
    private String getPattern(String str) {
        StringBuilder sb = new StringBuilder();
        HashMap<Character, Integer> charIndexMap = new HashMap<>();
        int index = 0;
        for (char c : str.toCharArray()) {
            charIndexMap.putIfAbsent(c, index++);
            sb.append(charIndexMap.get(c)).append(",");
        }
        return sb.toString();
    }
}

内容的提问来源于stack exchange，提问作者smalliebigs30