Java判断两字符串是否互为排列的问题排查及替代方案咨询

嘿，我来帮你排查问题并给出可行的解决方案！你的需求是判断两个字符串是否互为排列（即其中一个重排后能完全匹配另一个），但当前代码逻辑有明显漏洞，还遇到了无法使用Arrays.sort的限制，咱们一步步来解决：

先说说你现有代码的问题 #

• 逻辑错误：你的双层循环只是检查第一个字符串的每个字符是否在第二个字符串中存在，但完全没有考虑字符出现的次数。比如"aab"和"abb"，你的代码会返回true，但它们并不是互为排列——因为a和b的出现次数不一致。
• 输入处理bug：s.nextInt()读取完测试用例数后，会留下一个换行符，后续的s.nextLine()会直接读取这个换行符，导致第一个name1变成空字符串，这也会影响测试结果。

不用Arrays.sort的替代方案：字符计数法 #

这是判断字符串排列相等的经典高效方法，核心思路是统计两个字符串中每个字符的出现次数，若完全一致则互为排列。具体步骤：

1. 先检查两个字符串长度，长度不同直接返回false（长度不一样肯定不可能是排列）。
2. 创建一个长度为256的数组（覆盖所有ASCII字符），统计第一个字符串的字符出现次数。
3. 遍历第二个字符串，将计数数组对应位置的数值减1。
4. 最后检查计数数组是否全为0，是则说明字符出现次数完全匹配。

修正后的完整代码 #

class TestClass { 
    public static void main(String args[] ) throws Exception { 
        Scanner s = new Scanner(System.in); 
        int cases = s.nextInt(); 
        s.nextLine(); // 吃掉nextInt()后的换行符，避免读取空字符串
        for(int i=0; i<cases; i++){ 
            String name1 = s.nextLine().trim(); // 去除首尾空格，避免输入干扰
            String name2 = s.nextLine().trim(); 
            
            // 长度不同直接排除
            if(name1.length() != name2.length()){
                System.out.println(false);
                continue;
            }
            
            // 初始化字符计数数组
            int[] charCount = new int[256];
            for(char c : name1.toCharArray()){
                charCount[c]++;
            }
            
            // 遍历第二个字符串，减少对应字符的计数
            for(char c : name2.toCharArray()){
                charCount[c]--;
                // 提前终止：如果出现负数，说明该字符在第二个字符串中更多，直接跳出
                if(charCount[c] < 0){
                    break;
                }
            }
            
            // 检查所有字符计数是否为0
            boolean isPermutation = true;
            for(int count : charCount){
                if(count != 0){
                    isPermutation = false;
                    break;
                }
            }
            
            System.out.println(isPermutation);
        }
        s.close();
    }
}

代码优势说明 #

• 时间效率：时间复杂度为O(n)（n为字符串长度），比排序法的O(n log n)更高效。
• 适配限制：完全不需要使用Arrays.sort，完美适配HackerEarth的编辑器要求。
• 输入健壮性：处理了换行符和多余空格的问题，避免了输入导致的错误。

测试"majnu jamnu"这个用例时，两个字符串长度相同，每个字符的出现次数都是1，计数数组最终全为0，会输出true，符合预期。

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