Estoy tratando de crear una escalera de palabras, usando una lista enlazada como diccionario de palabras y una cola para contener la palabra que se va a cambiar.

En el bucle while de la cola, llega a la primera palabra del diccionario (la palabra "toon" y se cambia a "poon") y se detiene. ¿Cómo puedo hacer que continúe hasta que llegue a la palabra de destino?

Aquí está el código:

#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;

struct Node
{
    string data;
    Node* next;
};

void insert(string ele, Node*& head)
{
    Node* newnode = new Node;
    newnode->data = ele;
    newnode->next = head;
    head = newnode;
}

void del(string key, Node*& head)
{
    Node* temp = head;
    Node* prev = NULL;

    if (temp != NULL && temp->data == key)
    {
        head = temp->next; 
        delete temp;            
        return;
    }
    else
    {
        while (temp != NULL && temp->data != key)
        {
            prev = temp;
            temp = temp->next;
        }
        if (temp == NULL)
            return;

        prev->next = temp->next;

        delete temp;
    }
}

bool find(string key,Node *&head)
{
    Node* p = head;
    while (p != NULL)
    {
        if (p->data == key)
        {
            return true;
        }
        else
        {
            p = p->next;
        }
    }
    if (p == NULL)
        return false;
}

void print(Node*& head)
{
    Node* p = head;
    while (p != NULL)
    {
        cout << p->data;
        p = p->next;
    }
}

void WordLadder(string start, string target, Node*& head)
{
    if (start == target)
        cout << "They are the same";

    if (find(target, head) != true)
        cout << "Target Not found in dicionary";
    //start word size
    int wordlength = start.size();
    //counter
    int level = 0;
    queue<string> q;
    //push word in queue
    q.push(start);
    int len = 0;
    while (!q.empty())
    {
        int wordlength = start.size();
        int sizeofq = q.size();
       
        string word = q.front();
        q.pop();
        for (int i = 0; i < wordlength ; i++)
        {
            for (char c = 'a'; c <= 'z'; c++)
            {
                word[i] = c;
                   
                if (word == target)
                {
                    q.pop();
                }
                if (find(word, head) == true)
                {
                    del(word, head);
                    q.push(word);
                    break;
                }
            }
        }
    }
    cout << len;
}

int main()
{
    Node* head = NULL;
    insert("poon", head);
    insert("plee", head);
    insert("same", head);
    insert("poie", head);
    insert("plie", head);
    insert("poin", head);
    insert("plea", head);
    string start = "toon";
    string target = "plea";
    
    WordLadder(start, target, head);
   
    return 0;
}
0
Crossplayer 7 may. 2021 a las 23:15

2 respuestas

La mejor respuesta

Algoritmo

Parece que estaba en el camino correcto, tratando de implementar algo como BFS, así que no voy a explicar el algoritmo para una "Escalera de palabras" en detalle. Pero una descripción general de alto nivel es:

  1. Empuje la palabra de inicio en la cola
  2. Ejecute un ciclo hasta que la cola esté vacía
  3. Recorra todas las palabras que difieren en un solo carácter hasta la palabra actual y empuje la palabra en la cola (para BFS)
  4. Repita hasta que encontremos la palabra objetivo o repasemos todas las palabras.

Los errores que cometió y cómo los solucioné:

Antes del bucle "wordlength", necesita un bucle para pasar por todos los elementos de la cola. Si bien parece que el bucle while está haciendo eso, no es así. Creo que te das cuenta de esto, ya que creaste una variable sizeofq y nunca la usaste. El bucle se ve así:

for(int j = 0; j < sizeofq; j++) {

Y encapsula los siguientes dos bucles. También necesita agregar una variable temporal para almacenar el estado inicial de word[i]. También cometió algunos errores en los que utilizó la variable incorrecta.

Como se discutió en los comentarios, pasé de usar la lista vinculada personalizada que hizo a una std::set, pero puede volver a usarla fácilmente si lo necesita, ya que parece que no fue la que causó problemas. Aquí está el código completo:

#include <iostream>
#include <queue>
#include <string>
#include <set>
using namespace std;

void WordLadder(string start, string target, set<string>& myset)
{
    if(start == target) {
        cout << "They are the same" << "\n";
        return;
    }

    if(myset.find(target) == myset.end()) {
        cout<<"Target Not found in dicionary" << "\n";
        return;
    }
    
    int wordlength = start.size();
    int level = 0;

    queue<string> q;
    q.push(start);

    while (!q.empty())
    {
        level++;
        int sizeofq = q.size();
        for(int j = 0; j < sizeofq; j++) {
            string word = q.front();
            q.pop();
            for(int i = 0; i < wordlength; ++i) 
            {
                char temp_ch = word[i];
                for (char c = 'a'; c <= 'z'; c++)
                {
                    word[i] = c;
                    if (word == target) 
                    {            
                        cout << level + 1 << endl;
                        return;
                    }
                    if (myset.find(word) == myset.end())
                    {
                        continue;
                    }
                    myset.erase(word);
                    q.push(word);
                }

                 word[i] = temp_ch;
            }
            
        }      
    }

    return;   
}


int main()
{
   
    std::set<string> myset;
    myset.insert("poon");
    myset.insert("plee");
    myset.insert("same");
    myset.insert("poie");
    myset.insert("plie");
    myset.insert("poin");
    myset.insert("plea");
    string start = "toon";
    string target = "plea";
    
    WordLadder(start, target, myset);
    return 0;
} 

Sugerencias estilísticas

Pareces ser un nuevo programador de C ++, así que pensé en dejar mis pensamientos sobre el código aquí.

Se considera una buena práctica tener la función return como resultado, no imprimirlo. Hace que su código sea mucho más flexible.

Implementaste tu propio contenedor para que esto funcione, que es como reinventar la rueda. El STL de C ++ casi siempre incluye algo que puede usar para hacer su vida más fácil, así que búsquelo antes de ponerse a trabajar.

Si estás escribiendo un proyecto más grande, no uses using namespace, pero para un juguete pequeño como este está bien.

0
Misty 7 may. 2021 a las 21:56

Como ya dije en una de mis respuestas, enrollar sus propios contenedores en C ++ a menudo conduce a un código confuso y difícil de leer, lo que no ayuda en absoluto al modelar un problema.

En C ++ moderno (es decir, después de C ++ 11, y hoy en día lo ideal sería utilizar C ++ 17 o incluso empezar tímidamente a incursionar con C ++ 20) casi nunca necesita cosas como operator new, NULL ya menudo punteros (aunque siguen siendo útiles como una solución provisional para la falta de std::optional<T&>).

Por cierto, no creo que sea necesario utilizar una cola para resolver su problema; una sola variable "elemento actual" es suficiente; luego puede encontrar el siguiente elemento buscando en la lista qué cadena tiene una distancia Hamming de uno del elemento actual. No funcionará en un caso general debido a la probabilidad de bucles, pero es suficiente si solo está trabajando en una lista limitada de palabras como la suya donde en realidad solo hay una única escalera posible.

Así es como modelaría rápidamente su problema en C ++ 20:

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <ranges>
#include <stdexcept>
#include <string>
#include <string_view>
#include <vector>

using namespace std::literals;

// Simple implementation of Hamming's distance (see https://en.wikipedia.org/wiki/Hamming_distance)
std::size_t hamming_distance(const std::string_view s1, const std::string_view s2) {
    std::size_t dist {};

    if (s1.size() != s2.size()) {
        throw std::runtime_error { "strings have different lengths, which is unsupported" };
    }

    auto it1 { s1.begin() };
    auto it2 { s2.begin() };

    const auto end1 { s1.end() };

    while (it1 != end1) {
        dist += *it1++ != *it2++;
    }

    return dist;
}

bool word_ladder(std::string_view start, const std::string_view target, std::vector<std::string> words) {
    if (start == target) {
        std::cout << "noop: start and target are the same\n";
        
        return true;
    }

    // C++20's ranges - use std::find(std::begin(words), std::end(words), target) in older revisions
    if (std::ranges::find(words, target) == std::end(words)) {
        std::cerr << "error: target Not found in dictionary\n";

        return false;
    }

    std::size_t len { 1U };

    // Current word in the ladder - must be string because we are deleting them from the vector,
    // so we must copy them
    std::string word { start };

    std::cout << word;

    while (word != target) {
        std::cout << "->";

        // find an element in the dictionary has hamming(el, word) == 1 (i.e. 'cord' and 'core').
        // this won't work if there's more than one match, because it will cause a loop.
        // This is also based on C++20's ranges, and it can be replaced with std::find_if
        const auto next_it { std::ranges::find_if(words, [word] (const auto el) { return hamming_distance(el, word) == 1; }) };

        // no match, it means the chain can't be completed
        if (next_it == std::end(words)) {
            std::cout << "X (no result)\n";

            return false;
        }

        // print the next element
        std::cout << *next_it;
      
        // set the next word as the newly found item
        word = *next_it;

        // remove it from the vector
        // while this is O(n), it's empirically as fast as using a more "optimized" container
        // due to how hecking fast vectors and memcpy are on modern CPUs
        words.erase(next_it); 

        ++len; // chain length counter
    }

    std::cout << "\nChain was " << len << " elements long\n";

    return true;
}

int main() {
    std::vector<std::string> words {
        "poon",
        "plee",
        "same",
        "poie",
        "plie",
        "poin",
        "plea",
    };

    const auto start { "toon"sv };
    const auto target { "plea"sv };
    
    const bool success { word_ladder(start, target, std::move(words)) };
   
    return success ? EXIT_SUCCESS : EXIT_FAILURE;
} 

La salida es:

toon->poon->poin->poie->plie->plee->plea
Chain was 7 elements long

He usado std::vector en lugar de un contenedor más "óptimo" porque a menudo es la mejor opción general, incluso en sistemas muy limitados, debido a la velocidad de las CPU modernas. Las listas enlazadas son especialmente terribles y deberían (casi) evitarse siempre debido a su enorme sobrecarga de las indirecciones de punteros, que contrarrestan cualquier beneficio teórico que pueda obtener de ellas.

En general, generalmente debe usar vectores y hashmaps (es decir, std :: unordered_map) de forma predeterminada, y solo considerar los otros contenedores cuando realmente los necesite.

0
mcilloni 7 may. 2021 a las 22:22