Tengo mi código que devuelve las eliminaciones de enteros más pequeñas necesarias para hacer un anagrama:

#include <bits/stdc++.h>

using namespace std;

int makeAnagram(string a, string b) {
    int count = 0;
    for(auto it=a.begin(); it!=a.end(); it++){
        if(find(b.begin(), b.end(), *it) == b.end()){
            a.erase(it);
            count++;
        }
    }
    for(auto it = b.begin(); it != b.end(); it++){
        if(find(a.begin(), a.end(), *it) == a.end()){
            b.erase(it);
            count++;
        }
    }
    return count;
}

Y no funciona en absoluto, no entiendo por qué, la prueba principal es:

int main()
{

    string a={'a','b','c'};

    string b={'c','d','e'};

    int res = makeAnagram(a, b);

    cout << res << "\n";

    return 0;
}

Se supone que la consola devuelve 4, pero en su lugar devuelve 2, y las cadenas ayb tienen 2 elementos al final del programa, cuando deberían ser de tamaño 1

c++
0
Elezan Hita 14 ago. 2020 a las 10:27

2 respuestas

La mejor respuesta

El problema con su enfoque es que está eliminando el elemento durante la iteración pero no está considerando el cambio en el iterador i, e primero debe incrementar el iterador y luego eliminar el elemento anterior aquí es un enfoque simple

int makeAnagram(string a, string b) {
    int A = a.size();
    int B = b.size();
    int count = 0;
    if (A > B)
    {
        for (auto i = b.begin(); i != b.end(); i++)
        {
            size_t t = a.find(*i);
            if (t == std::string::npos)
            {
                count++;
            }
            else
            {
                a.erase(a.begin() + t);
            }
            
        }
       
        count = count + A - (b.size() - count);
        
    }
    else
    {for (auto i = a.begin(); i != a.end(); i++)
        {
            size_t t = b.find(*i);
            if (t == std::string::npos)
            {
                count++;
            }
            else
            {
                b.erase(b.begin() + t);
            }
            
        }
       
        count = count + B - (a.size() - count);
    }
    return count;
}
0
Arjun U S 14 ago. 2020 a las 10:39

Hm, pensé que ya había respondido a esta pregunta en otro lugar. Pero de todos modos. Intentemoslo de nuevo. Importante es el algoritmo. Y casi dudo que haya una respuesta más rápida que la mía a continuación. Pero nunca lo sabremos. . .

Y, como siempre, lo más importante es encontrar un buen algoritmo. Y luego, tal vez podamos hacer una buena codificación para obtener una solución rápida. Pero lo más importante es el algoritmo.

Empecemos a pensar en ello. Comencemos con 2 cadenas simples

abbccc
abbccc

Son idénticos, por lo que no hay nada que borrar. El resultado es 0. Pero, ¿cómo podemos llegar a esta conclusión? Podríamos pensar en clasificar, buscar, comparar carácter por carácter, pero el enfoque correcto es contar la aparición de caracteres. Eso se hace cada vez que se habla de anagramas. Entonces, aquí tenemos para cada cadena 1 a, 2 b, 3c.

Y si comparamos los recuentos de cada carácter en las cadenas, entonces son los mismos.

Si recordamos nuestros -mucho tiempo atrás- días escolares o el código C, o incluso mejores códigos de ensamblador de microcontroladores, entonces sabemos que la comparación se puede hacer restando. Ejemplo. Veamos algunos ejemplos: 6-4 = 2 o 3-4 = -1 o 7-7 = 0. Entonces, ese enfoque se puede utilizar.

Siguiente ejemplo para 2 cadenas:

 bbcccddd
abbccc

Al mirarlo, ya vemos que necesitamos eliminar 3 * "d" de la primera cadena y una "a" de la segunda cadena. En total 4 eliminaciones. Veamos los conteos: Cadena a: b-> 2, c-> 3 d-> 3, Cadena b: a-> 1, b-> 2, c-> 3

Y ahora comparemos, entonces reste: a-> 0-1 = -1, b-> 2-2 = 0, c-> 3-3 = 0, d-> 3-0 = 3.

Y si sumamos los valores absolutos de los deltas, tenemos el resultado. 3 + abs (-1) = 4

Bien, ahora podemos empezar a codificar este algoritmo.

  1. Lea 2 cadenas fuente ayb de std::cin. Para esto usaremos std::getline
  2. A continuación, definimos un "contador" como una matriz. Suponemos que un carácter tiene un ancho de 8 bits y que el número máximo de caracteres es 256
  3. Contamos positivamente todas las apariciones de caracteres de la primera cadena
  4. Ahora hacemos la comparación y el conteo en un paso, disminuyendo el contador por cada aparición de un carácter en la segunda cadena.
  5. Luego acumulamos todos los contadores (para todas las apariciones de caracteres). Usamos el valor absoluto, porque los números pueden ser negativos.

Entonces tenemos el resultado.

Tenga en cuenta que solo necesitaría un tamaño de matriz de 26 contadores, porque los requisitos establecen un rango de entrada para 'a' - 'z' para los caracteres de las cadenas. Pero luego necesitaríamos mapear los valores de los caracteres para 'a' - 'z' a índices 0-25, restando siempre 'a' de un carácter. Pero con un poco de desperdicio de espacio (230bytes), podemos omitir la resta.

Por favor mira:

#include <iostream>
#include <string>

int main() {

    // Here we will store the input, 2 strings to check
    std::string a{}, b{};

    // Read the strings from std::cin
    std::getline(std::cin, a);
    std::getline(std::cin, b);

    // Here we will count the occurence of characters. 
    //We assume a char type with a width of 8 bit
    int counter[256]{};

    // Count occurence of characters in string a
    // And Count occurence of characters in string b negatively
    for (const char c : a) ++counter[c];
    for (const char c : b) --counter[c];

    // Calculate result
    int charactersToDeleteForAnagram{};
    for (int c : counter) charactersToDeleteForAnagram += std::abs(c);

    std::cout << charactersToDeleteForAnagram << '\n';

    return 0;
}

También podemos convertir a C ++, donde usamos la verificación de entrada, un std::unordered_map para contar y std::accumulate para resumir. Además, la representación interna de un tipo char no importa. Y el principio es el mismo.

No sé si esto es mucho más lento. . .

Por favor mira:

#include <iostream>
#include <string>
#include <unordered_map>
#include <numeric>

int main() {

    // Here we will store the input, 2 strings to check
    std::string aString{}, bString{};

    // Read the strings from std::cin
    if (std::getline(std::cin, aString) && std::getline(std::cin, bString)) {

        // Here we will count the occurence of characters. 
        //We assume a char type with a width of 8 bit
        std::unordered_map<char, int> counter{};

        // Count occurence of characters in string a
        // And Count occurence of characters in string b negatively
        for (const char character : aString) counter[character]++;
        for (const char character : bString) counter[character]--;

        // Calculate result and show to user
        std::cout << std::accumulate(counter.begin(), counter.end(), 0U, 
            [](size_t sum, const auto& counter) { return sum + std::abs(counter.second); }) << '\n';
    }
    else std::cerr << "\nError: Problem with input\n";
    return 0;
}

Si tiene alguna pregunta, por favor pregunte.


Idioma: C ++ 17

Compilado y probado con MS Visual Studio 2019 Community Edition

0
Armin Montigny 14 ago. 2020 a las 13:11