Spoj anagramy AL_23_02

Question

Rozwiązuję zadanie na spoj: https://pl.spoj.com/problems/AL_23_02/. Napisałem rozwiązanie w pythonie. Testuję algorytm i wydaje mi się, że wyniki są zwracane prawidłowo. 

Sędzia na spoj zwraca: Błędna odpowiedź.

Jest to jedno z pierwszych zadań na spoj, proszę o wskazówki, co zrobiłem źle.

Rozwiązanie: 

n = int(input())

if n <= 1000:
    for i in range(n):
        str1, str2 = input().split()

        str1Map = {}
        str2Map = {}
        amountOfOperation = 0
        lenStr1 = len(str1)
        lenStr2 = len(str2)

        for el in str1:
            if el not in str1Map:
                str1Map[el] = 1
            else:
                str1Map[el] = str1Map[el]+1

        for el in str2:
            if el not in str2Map:
                str2Map[el] = 1
            else:
                str2Map[el] = str2Map[el] + 1

        if lenStr1 < lenStr2:
            temp = str1Map
            str1Map = str2Map
            str2Map = temp
        for key in str1Map:
            if key in str2Map:
                difference = abs(str1Map[key] - str2Map[key])
                if lenStr1 != lenStr2:
                    amountOfOperation += difference
                elif str1Map[key] > str2Map[key]:
                    amountOfOperation += difference
            else:
                amountOfOperation += str1Map[key]
        print(amountOfOperation)

 

Answer 1

Nie do końca rozumiem te ify z ostatnich linijek, ale mogę powiedzieć jak wygląda mój pomysł na rozwiązanie.

Będziemy tak samo jak Ty liczyli ilość wystąpień liter w poszczególnych stringach (nazwijmy te stringi A i B). Następnie przejdziemy po wszystkich literach alfabetu. Powiedzmy, że aktualnie rozważamy literę x. Pomniejszamy ilość wystąpień litery x w słowie A i B o minimalną ilość wystąpień tej litery w słowach A i B. Czyli jeżeli x wystąpiło np. 5 razy w A i 3 w B to od 5 odejmujemy 3 a od 3, 3. Zrobiliśmy to dlatego, bo te 3 litery są na dobrych pozycjach i nigdy nie musimy ich zmieniać. Teraz zostanie nam jakaś reszta dla A i B. W poprzednim przykładzie te reszty wynoszą 5-3=2, 3-3=0. Trzymamy liczniki dla słowa A i B, które będą trzymały sumę reszt dla wszystkich liter w słowie A lub B. Czyli w tym przypadku sumę reszt dla A zwiększamy o 2, a sumę reszt dla B o 0. Po tym jak przejdziemy po wszystkich literach, wynikiem będzie maksimum z sumy reszt dla A i sumy reszt dla B.

Wynika to z tego, że jeżeli sumy reszt dla A i B są równe to oznacza, że wykonamy tylko operacje zamiany litery. Jeżeli suma reszt A jest większa to oznacza to że dodatkowo wykonamy kilka operacji usunięcia litery ze słowa A, a jeżeli suma reszt A jest mniejsza to oznacza to, że kilka liter trzeba dodać do A.

Tak to wygląda w c++:

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

int num_tests, cnt_A, cnt_B;
string A, B;

int main()
{
    cin >> num_tests;

    while(num_tests--)
    {
        cin >> A >> B;
        map<int, int> m_A, m_B;
        cnt_A = cnt_B = 0;

        for(int i = 0; i < A.length(); i++)
            m_A[A[i]-'a']++;

        for(int i = 0; i < B.length(); i++)
            m_B[B[i]-'a']++;

        for(int k = 0; k < 26; k++)
        {
            int minim = min(m_A[k], m_B[k]);
            m_A[k] -= minim, m_B[k] -= minim;

            cnt_A += m_A[k], cnt_B += m_B[k];
        }

        cout << max(cnt_A, cnt_B) << "\n";
    }
}