用Stack实现字符串重排回文判断，代码未通过隐藏测试求排查

问题描述 #

给定一个字符串，判断其字符能否重排为回文。示例：输入"aabb"时应返回true（可重排为"abba"），但以下代码未通过2个隐藏测试，需排查错误。

待排查代码 #

boolean solution(String inputString) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < inputString.length(); i++) {
        Character curr = inputString.charAt(i);
        if (stack.contains(curr) == false) {
            stack.push(curr);
        }
        else {
            stack.pop();
        }
    }
    if ((stack.size() == 0) || (stack.size() == 1)) {
        return true;
    }
    return false;
}

错误原因 #

你的代码逻辑存在根本性问题：

• Stack.contains(curr)会检查栈中是否存在该字符，但stack.pop()只会弹出栈顶元素，而不是弹出与curr对应的那个元素。
• 举个反例：输入"abab"，遍历过程如下：
  1. 第一个a：栈为空，push → 栈内容[a]
  2. 第二个b：栈中无b，push → 栈内容[a, b]
  3. 第三个a：栈中有a，执行pop → 弹出栈顶的b，栈内容[a]
  4. 第四个b：栈中无b，push → 栈内容[a, b]
• 最终栈大小为2，返回false，但实际上"abab"可以重排为"abba"（回文），正确结果应为true，这就是代码失效的典型场景。

正确思路与修正代码 #

判断字符能否重排为回文的核心是字符出现次数的奇偶性：

• 若字符串长度为偶数：所有字符的出现次数必须是偶数
• 若字符串长度为奇数：恰好有一个字符的出现次数是奇数

修正代码（用HashMap统计次数） #

boolean solution(String inputString) {
    HashMap<Character, Integer> countMap = new HashMap<>();
    for (char c : inputString.toCharArray()) {
        countMap.put(c, countMap.getOrDefault(c, 0) + 1);
    }
    
    int oddCount = 0;
    for (int count : countMap.values()) {
        if (count % 2 != 0) {
            oddCount++;
            // 提前终止，超过1个奇数次直接返回false
            if (oddCount > 1) {
                return false;
            }
        }
    }
    return oddCount <= 1;
}

更高效的实现（用ASCII数组） #

如果输入仅包含ASCII字符，可以用数组代替HashMap，效率更高：

boolean solution(String inputString) {
    int[] charCounts = new int[128]; // 覆盖所有ASCII字符
    for (char c : inputString.toCharArray()) {
        charCounts[c]++;
    }
    
    int oddCount = 0;
    for (int count : charCounts) {
        if (count % 2 != 0) {
            oddCount++;
            if (oddCount > 1) {
                return false;
            }
        }
    }
    return oddCount <= 1;
}

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