Bestimmen Sie anhand von zwei Zeichenfolgen die Anzahl der gemeinsamen Zeichen zwischen ihnen.

Beispiel

Für s1 = "aabcc" und s2 = "adcaa" sollte die Ausgabe commonCharacterCount (s1, s2) = 3 sein.

Zeichenfolgen haben 3 gemeinsame Zeichen - 2 "a" s und 1 "c".

Ich habe mich ziemlich lange mit diesem Problem beschäftigt und viele Ansätze zur Lösung dieses Problems ausprobiert, aber ich kann es nicht ganz herausfinden. Ich habe die Grundidee, wie ich es lösen soll, aber ich kann das nicht auf Code übertragen.

Mein Ansatz ist es, die Zeichen der Zeichenfolge in ihre eigene ArrayList zu setzen und verschachtelte Schleifen zu verwenden, um sie zu durchlaufen, die ähnlichen Zeichen zu vergleichen und die Anzahl in einem int-Wert zu speichern. Ich habe keinen Code, weil ich viele verschiedene Versuche unternommen habe, meinen Code zu variieren, aber kein Glück.

Ich habe zwei verschachtelte for-Schleifen verwendet, die wie folgt voneinander getrennt sind:

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

Und

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

Nachdem diese Schleifen ausgeführt wurden, gebe ich die Differenz zwischen den beiden Buchstaben in Common Ints abhängig von ihrer Größe zurück, um Negative zu vermeiden. Also, wenn LettersInCommon> LettersInCommon2 - LettersInCommon - LettersInCommon2 zurückgeben; und umgekehrt.

Ich möchte nicht, dass mir jemand sagt, wie ich das codieren soll. Ich möchte nur Ratschläge zu meiner Logik, um zu sehen, ob ich dieses Problem vereinfachen kann oder ob mir etwas fehlt.

Ich möchte auch sagen, dass dieser Code für einige Testfälle funktioniert, aber nicht für alle.

Ich habe die Kommentare berücksichtigt, die ich erhalten habe und die ich bisher erhalten habe:

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

Ich bin sehr nah dran, aber der Fehler, den ich bekomme, ist eine Ausnahme außerhalb der Grenzen in dieser Zeile secondString.remove(s2.indexOf(c));

Hat jemand einen Einblick dazu?

2
user9372262 16 Apr. 2018 im 19:39

4 Antworten

Beste Antwort

Sie könnten Karten holen. Es ist vielleicht nicht die beste Lösung in Bezug auf die Leistung, aber eine, die intuitiv zu verstehen ist. Iterieren Sie zunächst jede Zeichenfolge und sammeln Sie jedes ihrer (unterschiedlichen) Zeichen mit ihrer Anzahl an Erscheinungsbildern. Vergleichen Sie dann die Keysets beider Karten (d. H. Die Zeichen) und speichern Sie sie für jedes Zeichen, das Sie in beiden Karten finden, zusammen mit der minimalen Anzahl von Erscheinungsbildern aus beiden Karten. Also so etwas wie das:

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

Ich denke, dies könnte mit der Stream-API auf coole Weise implementiert werden, aber es wäre eine ziemlich komplexe Aussage, nicht sicher, ob Sie Erfahrung mit Streams haben.

Bearbeiten: Hier ist eine Lösung mit Streams. Ich wette, es gibt bessere, sowohl in Bezug auf die Leistung als auch in Bezug auf den Ansatz, aber es ist das erste, was ich versucht habe:

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;
}
2
user3237736 16 Apr. 2018 im 17:29
  1. Vergleiche keine Objekte mit ==
  2. Das Rad nicht neu erfinden: Sie müssen keine Liste durchlaufen, um festzustellen, ob sie ein Element enthält. Es gibt contains(), um das für Sie zu tun.
  3. Sie brauchen nicht einmal contains(), da remove() Ihnen sagt, ob etwas entfernt wurde oder nicht. Alles was Sie brauchen ist:

    1. Erstellen Sie ein List<Character> aus string2
    2. Durchlaufen Sie die Zeichen von string1 oder bis die Liste leer ist
    3. Entfernen Sie bei jeder Iteration das aktuelle Zeichen aus der Liste. Wenn es entfernt wurde, erhöhen Sie die Anzahl
1
JB Nizet 16 Apr. 2018 im 16:47

Erstellen Sie für jede Zeichenfolge, die Sie eingeben, eine Karte mit den Buchstabenzahlen. Vergleichen Sie dann die Schlüssel miteinander und nehmen Sie die niedrigste Anzahl aus den beiden Karten, wenn der Buchstabe in beiden Wörtern enthalten ist. Versuche dies

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

Ausgabe

Common Character a : 1
Common Character b : 1
Common Character c : 2
0
RAZ_Muh_Taz 16 Apr. 2018 im 17:09

Verwenden Sie den s1.charAt(i) == s2.charAt(i) Vergleich. Es ist nicht erforderlich, die Zeichenfolgen in eine ArrayList einzufügen.

Bearbeiten: Sie müssen eine bedingte Anweisung hinzufügen, um sicherzustellen, dass Sie keine Grenzen überschreiten, wenn die Zeichenfolgen unterschiedlich lang sind.

0
Raymo111 16 Apr. 2018 im 20:34