我有 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]
}
}
我相信你需要调整你的守卫条件
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;