查找字符串是否可以是字谜词

Question

我有 String

s1

和 String

s2

，这对

s1

，

s2

被称为特殊字符串，如果我们可以通过从每个字符串

s1

中删除单个字符（任意次数）来使它们成为变位词，并且

s2

。

示例：

s1 = safddadfs
s2 = famafmss

Result = True

说明：

s1 has a=2, d=2, f=2, s=2
s2 has a=2, d=2, m=2, s=2

We can remove 'f' from s1 and remove 'm' from s2 to make them anagrams. 
so  s1 becomes a=2, d=2, s=2
and s2 becomes a=2, d=2, s=2

示例：

s1 = aaabb
s2 = aabbb

Result = True

说明：

s1 has a=3, b=2 
s2 has a=2, b=3

We can single 'a' from s1 and remove single 'b' from s2 to make them anagrams. 
so  s1 becomes a=2, b=2
and s2 becomes a=2, b=2

示例：

s1 = aab
s2 = ab

Result = True

说明：

s1 has a=2, b=1 
s2 has a=1, b=1

We can single 'a' from s1 and nothing from s2 to make them anagrams. 
so  s1 becomes a=1, b=1
and s2 becomes a=1, b=1

我尝试实现此代码，但对于 s1 =“aaabb”和 s2 =“aabb”的测试用例失败

我无法理解解决此问题的正确逻辑。

import java.util.*;

public class Main {

    public static boolean solve(String s1, String s2) {
        Map<Character, Integer> m1 = getCountMap(s1);
        Map<Character, Integer> m2 = getCountMap(s2);
        boolean valid = canBeAnagrams(m1, m2);
        
        if(!valid) {
            valid = canBeAnagrams(m2, m1);
        }
        return valid;
    }

    private static boolean canBeAnagrams(Map<Character, Integer> m3, Map<Character, Integer> m4) {
        int count = 0;
        Map<Character, Integer> m1 = new HashMap<>(m3), m2 = new HashMap<>(m4);
        for(char c : m1.keySet()) {
            int v1 = m1.get(c);
            int v2 = m2.getOrDefault(c,0);
            if(v1 != v2) {
                count++;
            }
            m2.remove(c);
            if(count > 1) return false;
        }   
        if(m2.size() > 1) return false;
        return true;
    }

    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"));  // Should print [True]
        System.out.println(solve("aaabb", "aabbb"));  // Should print [True], but getting false
        System.out.println(solve("aab", "ab"));  // Should print [True]
    }
}

Answer 1

我相信你需要调整你的守卫条件

canBeAnagrams

:

        ...

        // Two mismatches are OK, but on the third - we should return a false
        if(count > 2) return false;
    }
    
    // Here we should not forget about the previous number of errors and sum it up with number of items left in m2
    if(count + m2.size() > 2) return false;