java获取两个字符串之间的公共字符计数

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);
            }
        }
}

因此，在这些循环运行之后，我返回两个字母sincommon int之间的差异，这取决于它们的大小，以避免出现负片。所以如果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

使用s1.charAt(i) == s2.charAt(i)比较。无需将字符串放入arrayList

编辑：需要添加一个条件语句，以确保字符串长度不同时不会越界

Answer 2

为你给它的每个字符串创建一个字母计数图。然后将两个键相互比较，如果两个单词中都包含字母，则从两个地图中获取最低计数。试试这个

public static void main(String[] args)
{
    String str1 = "aabbcc";
    String str2 = "abcddc";
    HashMap<Character, Integer> str1LetterCounts = createLetterCountMap(str1);
    HashMap<Character, Integer> str2LetterCounts = createLetterCountMap(str2);

    HashMap<Character, Integer> commonCounts = new HashMap<>();

    Set<Character> possibleCommonCharacterList = str1LetterCounts.keySet();

    for(Character letter : possibleCommonCharacterList)
    {
        if(str2LetterCounts.containsKey(letter))
        {
            Integer count1 = str1LetterCounts.get(letter);
            Integer count2 = str2LetterCounts.get(letter);
            commonCounts.put(letter, count1 <= count2 ? count1 : count2);
            System.out.println("Common Character " + letter + " : " + (count1 <= count2 ? count1 : count2));
        }
    }

}

public static HashMap<Character, Integer> createLetterCountMap(String word)
{
    HashMap<Character, Integer> letterCountsForWord = new HashMap<>();
    for(int i = 0; i < word.length(); i++)
    {
        Character key = word.charAt(i);
        if(letterCountsForWord.containsKey(key))
        {
            letterCountsForWord.put(key, letterCountsForWord.get(key) + 1);
        }
        else
            letterCountsForWord.put(key, 1);
    }

    return letterCountsForWord;
}

输出

Common Character a : 1
Common Character b : 1
Common Character c : 2

Answer 3

你可以找地图。就性能而言，这可能不是最好的解决方案，但在我看来，这是一个直观易懂的解决方案。首先，迭代每个字符串并收集其每个（不同的）字符及其外观计数。然后，比较两个贴图（即字符）的键集，对于在两个贴图中找到的每个字符，将其与两个贴图中的最小外观计数一起存储。比如：

// 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

我想这可以通过流API以一种很酷的方式实现，但这将是一个相当复杂的语句，不确定您是否有流方面的经验

编辑：这里有一个使用流的解决方案。我敢打赌，无论是从性能角度还是从其方法来看，都有更好的方法，但这是我尝试的第一件事：

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;
}