Java不使用import实现字符串Anagram（字母异位词）判断

实现要求 #

• 核心功能：对比2个字符串，判断二者包含的每类字符的数量是否完全一致
• 强制约束：禁止使用任何外部包，禁止通过import语句引入任何类

原有方案问题 #

初始方案逻辑为：将两个字符串拆分为字符数组，遍历第一个数组的字符，若在第二个数组中找到匹配字符就将其移除，遍历结束后第二个数组为空则判定匹配。
该逻辑在字符串存在重复字符时会出现匹配错误，例如输入"oellh"和"heloo"（正确结果应为false）时，原有流程会错误返回true：

• 匹配字符o：charsB更新为"hel"
• 匹配字符e：charsB更新为"hl"
• 匹配第一个字符l：charsB更新为"h"
• 匹配第二个字符l：未找到匹配字符，charsB保持为"h"
• 匹配字符h：charsB更新为""，最终得到错误的true结果

修复逻辑 #

采用位置标记法规避重复字符匹配错误：

1. 首先判断两个字符串长度，长度不等直接返回false
2. 将两个字符串转为原生char数组（无需依赖split方法，效率更高）
3. 初始化和第二个字符数组等长的boolean标记数组，记录第二个数组中哪些位置的字符已经被匹配过，避免重复匹配同一位置的字符
4. 遍历第一个数组的每个字符，在第二个数组中查找未被标记匹配、且字符值相等的第一个位置，找到则标记该位置为已匹配；如果遍历完第二个数组都没找到对应字符，直接返回false
5. 所有字符都完成匹配则返回true

完整补全代码 #

static boolean isAnagram(String a, String b) {
    // 长度不相等直接判定不匹配
    if(a.length() != b.length()){
        return false;
    }
    
    char[] charsA = a.toCharArray();
    char[] charsB = b.toCharArray();
    // 标记charsB对应索引位置的字符是否已经被匹配，避免重复字符匹配错误
    boolean[] bMatchedFlag = new boolean[charsB.length];
   
    for (int i = 0; i < charsA.length; i++) {
        int matchIndex;
        // 查找当前字符在charsB中第一个可用的匹配位置
        for (matchIndex = 0; matchIndex < charsB.length; matchIndex++) {
            if (!bMatchedFlag[matchIndex] && charsA[i] == charsB[matchIndex]) {
                bMatchedFlag[matchIndex] = true;
                break;
            }
        }
        // 没找到匹配字符，直接返回false
        if (matchIndex == charsB.length) {
            return false;
        }
    }
    
    // 所有字符都完成匹配
    return true;
}

测试用例验证 #

测试输入：

"hello", "olhel"   // case one
"helloq", "olhel"  // case two
"helloq", "olheln" // case three

运行输出：

true              // case one：字符种类、数量完全一致
false             // case two：字符串长度不等
false             // case three：长度一致但字符组成不匹配

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