判断两字符串能否通过删字符变为变位词的代码问题排查

需求说明 #

给定两个字符串s1和s2，判断是否可通过从两个字符串中分别删除0个或多个字符，使剩余的字符串互为变位词（即字符种类和对应数量完全相同）。

示例说明 #

示例1 #

s1 = "safddadfs"
s2 = "famafmss"

Result = true

解释：s1包含2个'a'、2个'd'、2个'f'、2个's'；s2包含2个'a'、2个'm'、2个'f'、2个's'，删除s1的'd'和s2的'm'即可得到相同的字符串，互为变位词。

示例2 #

s1 = "aaabb"
s2 = "aabbb"

Result = true

解释：s1有3个'a'、2个'b'；s2有2个'a'、3个'b'，删除s1的1个'a'和s2的1个'b'，即可得到均为"aabb"的两个字符串，互为变位词。

示例3 #

s1 = "aab"
s2 = "ab"

Result = true

解释：删除s1的1个'a'，即可得到与s2相同的"ab"，互为变位词。

原代码问题分析 #

原代码的核心逻辑完全偏离需求：

1. canBeAnagrams函数错误地限制了“计数不同的字符不能超过1个”以及“独有的字符不能超过1个”，但题目允许删除任意数量的字符，只要最终剩余字符的计数完全相同即可，不存在上述限制。
2. 以示例2为例，两个字符串的'a'和'b'计数均不同，原代码会因计数不同的字符数超过1而返回false，与预期结果矛盾。
3. 原代码未正确理解“变位词”的实现逻辑：只要存在至少一个共同字符，就可以通过删除其他所有字符，只保留该字符的若干个（不超过两个字符串中的最小计数），得到互为变位词的结果。

修复方案 #

正确逻辑 #

两个字符串可通过删除得到变位词的条件为：

• 两个字符串存在至少一个共同字符（可保留该字符的若干个，删除其他所有字符）；
• 或两个字符串均可删为空字符串（空字符串互为变位词）。

修复后的代码 #

import java.util.HashMap;
import java.util.Map;

public class Main {

    public static boolean solve(String s1, String s2) {
        // 处理空字符串情况：均为空则返回true，仅一个为空则返回false
        if (s1.isEmpty() && s2.isEmpty()) return true;
        if (s1.isEmpty() || s2.isEmpty()) return false;

        Map<Character, Integer> countMap1 = getCountMap(s1);
        Map<Character, Integer> countMap2 = getCountMap(s2);

        // 检查是否存在共同字符
        for (char c : countMap1.keySet()) {
            if (countMap2.containsKey(c)) {
                return true;
            }
        }

        // 无共同字符，无法得到非空变位词
        return false;
    }

    private static Map<Character, Integer> getCountMap(String s) {
        Map<Character, Integer> countMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            countMap.put(c, countMap.getOrDefault(c, 0) + 1);
        }
        return countMap;
    }

    public static void main(String[] args) {
        System.out.println(solve("safddadfs", "famafmss"));  // 输出true
        System.out.println(solve("aaabb", "aabbb"));  // 输出true
        System.out.println(solve("aab", "ab"));  // 输出true
        System.out.println(solve("aaabb", "aabb"));  // 输出true
        System.out.println(solve("abc", "def"));  // 输出false
    }
}

代码说明 #

1. getCountMap函数保持不变，用于统计字符串中每个字符的出现次数。
2. solve函数先处理空字符串的边界情况，再遍历其中一个字符计数Map，检查是否存在另一个Map也包含的字符，若存在则直接返回true，否则返回false。

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