java - 获取两个字符串之间的公共(public)字符数

Question

Given two strings, find the number of common characters between them.

Example

For s1 = "aabcc" and s2 = "adcaa", the output should be commonCharacterCount(s1, s2) = 3.

Strings have 3 common characters - 2 "a"s and 1 "c".

我一直被这个问题困住了，我尝试了很多方法来解决这个问题，但我还是不太明白。我对如何解决它有主要想法，但我无法将其转化为代码。

我的方法是将字符串的字符放在它们自己的 ArrayList 中，并使用嵌套循环遍历它们，比较相似的字符并将计数存储在一个 int 值中。我没有任何代码，因为我尝试了许多不同的尝试来改变我的代码，但没有成功。

我使用了两个相互独立的嵌套 for 循环，如下所示:

for(int i = 0; i<firstString.size(); i++){
    for(int j = 0; j<secondString.size(); j++){
        if(firstString.get(i) == secondString.get(j){
            lettersInCommon++;
            secondString.remove(j);
            }
        }
}

和

for(int i = 0; i<secondString.size(); i++){
    for(int j = 0; j<firstString.size(); j++){
        if(firstString.get(i) == secondString.get(j){
            lettersInCommon2++;
            firstString.remove(i);
            }
        }
}

所以在这些循环运行之后，我根据它们的大小返回两个 lettersinCommon 整数之间的差异以避免负值。所以如果 lettersInCommon > lettersInCommon2 -- 返回 lettersInCommon - lettersInCommon2;反之亦然。

我不想让任何人告诉我如何编写代码，我只想对我的逻辑提出建议，看看我是否可以简化这个问题，或者我是否遗漏了什么。

我还想声明此代码适用于某些测试用例，但并非适用于所有测试用例。

到目前为止，我一直在考虑收到的评论:

ArrayList<Character> firstString = new ArrayList<Character>();
ArrayList<Character> secondString = new ArrayList<Character>();
int lettersInCommon = 0;

for(int i = 0; i<s1.length(); i++){
    firstString.add(s1.charAt(i));
}

for(int i = 0; i<s2.length(); i++){
    secondString.add(s2.charAt(i));
}
Collections.sort(firstString);
Collections.sort(secondString);
for(char c : firstString){
    if(firstString.contains(c) && secondString.contains(c)){
        lettersInCommon++;
        secondString.remove(s2.indexOf(c));
    }
}

我真的很接近，但我得到的错误是这一行的越界异常secondString.remove(s2.indexOf(c));

有没有人对此有任何见解？

Answer 1

你可以去找 map 。就性能而言，它可能不是最好的解决方案，但 imo 是一种直观易懂的解决方案。首先，迭代每个字符串并收集它的每个(不同的)字符及其出现次数。然后，比较两个 map (即字符)的键集，对于您在两个 map 中找到的每个字符，将其与两个 map 中的最小出现次数一起存储。所以像这样:

// first collect characters with their appearance count in maps:
"aabcc" -> 2xa, 1xb, 2xc
"adcaa" -> 3xa, 1xc, 1xd

// now, get all shared characters with their minimum count from both maps:
a -> min(2,3) = 2
b -> not shared
c -> min(2,1) = 1
d -> not shared

我想这可以使用 Stream API 以一种很酷的方式实现，但这将是一个相当复杂的语句，不确定您是否有使用 Streams 的经验。

编辑:这是使用 Streams 的一种解决方案。我敢打赌有更好的，无论是性能方面还是方法方面，但这是我尝试的第一件事:

public static void main(String[] args) {
    System.out.println(commonCharacterCount("aabcc","adcaa"));
}

public static int commonCharacterCount(String s1, String s2) {
    Map<Character, Integer> s1CharacterCount = getCharacterCount(s1);
    Map<Character, Integer> s2CharacterCount = getCharacterCount(s2);
    return s1CharacterCount.keySet().stream()
            .filter(s2CharacterCount.keySet()::contains)
            .mapToInt(c -> Math.min(s1CharacterCount.get(c), s2CharacterCount.get(c)))
            .sum();
}

public static Map<Character, Integer> getCharacterCount(String s) {
    Map<Character, Integer> characterCount = new HashMap<>();
    for (char c: s.toCharArray()) {
        characterCount.put(c, characterCount.computeIfAbsent(c, count -> 0) + 1);
    }
    return characterCount;
}