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

问题描述 投票：0回答：6

给定两个字符串，找出它们之间公共字符的数量。

示例

对于 s1 = "aabcc" 和 s2 = "adcaa"，输出应该是 commonCharacterCount(s1, s2) = 3.

字符串有 3 个公共字符 - 2 个“a”和 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 > lettersInCommon2 -- return 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));

有人对此有任何见解吗？

java arraylist
6个回答
2
投票

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

// 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;
}
1
投票
  1. 不要将物体与 
    ==
    2. 进行比较
  2. 不要重新发明轮子：您不需要循环遍历列表来知道它是否包含元素。 
    contains()
    可以为您做到这一点。

  3. 您甚至不需要

    contains()
    ，因为
    remove()
    会告诉您某些内容是否已被删除。所以你需要的是：

    1. 从 string2 
       创建一个
      List<Character>
    2. 循环 string1 的字符，或者直到列表为空
    3. 在每次迭代时，从列表中删除当前字符。如果它被删除，则增加计数
0
投票

为您提供的每个字符串创建字母计数图。然后将这些键相互比较，如果两个单词中都包含该字母，则从两个映射中获取最低计数。试试这个

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
0
投票

使用

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

编辑：您需要添加条件语句以确保当字符串长度不同时不会超出范围。

0
投票
int solution(String s1, String s2) {
    int count = 0;
    String[] arr1 = s1.split("");
    String[] arr2 = s2.split("");//I did split 2 Strings

    for (int i = 0; i < s1.length(); i++) {
        String s = arr1[i];//anymatch operator complaining if I directly give arr[i]
        if (Arrays.stream(arr2).anyMatch(t -> t.equals(s))) {
            for (int j = 0; j < arr2.length; j++) {
                if (arr2[j].equals(arr1[i])) {
                    arr2[j] = "";
                    break;
                }
            }
            arr1[i] = "";

            count++;
        }
    }
    return count;
}
0
投票

这是解决方案的另一种风格。另一位用户已经给出了相同的想法，只是语法稍微清晰（恕我直言）：

int solution(String s1, String s2) {
var m1 = s1.chars().mapToObj(value -> (char) value)
            .toList()
            .stream()
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

var m2 = s2.chars().mapToObj(value -> (char) value)
            .toList()
            .stream()
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
            
return m1.entrySet().stream().mapToInt(m1Entry -> {
        var m1Value = m1Entry.getValue().intValue();
        var m2Value = m2.getOrDefault(m1Entry.getKey(), 0L).intValue();
        return m1Value <= m2Value ? m1Value : m2Value;
}).sum();

}

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.