如何创建单词阶梯？

Question

我正在尝试创建一个单词阶梯，方法是使用链表作为单词字典，并使用队列来保存要更改的单词。

在队列的while循环中，到达字典的第一个单词（单词"toon"改成"poon"）就停止了。我怎样才能让它继续直到它到达目标词？

代码如下：

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

Answer 1

算法

看来你是在正确的轨道上，试图实现类似 BFS 的东西，所以我不打算详细解释“单词阶梯”的算法。但高级概述是：

压入队列中的起始词
运行循环直到队列为空
遍历所有与当前词只相差一个字符的词并将单词推入队列（对于 BFS）
重复直到找到目标词或遍历所有词

你犯的错误以及我如何修正它们：

在“wordlength”循环之前，您需要一个循环来遍历队列中的所有元素。虽然看起来 while 循环正在这样做，但事实并非如此。我想你意识到了这一点，因为你创建了一个 sizeofq 变量并且从未使用过它。循环看起来像这样：

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

并封装了接下来的两个循环。您还需要添加一个临时变量来存储 word[i] 的初始状态。您还犯了一些使用错误变量的错误。

正如评论中所讨论的那样，我从使用您制作的自定义链表切换到 std::set，但如果需要，您可以轻松切换回它，因为它似乎不是一个造成问题。这是完整的代码：

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

文体建议

你似乎是一个新的 C++ 程序员，所以我想我会在这里留下我对代码的想法。

使用函数 return 结果而不是打印结果被认为是一种很好的做法。它使您的代码更加灵活。

您实现了自己的容器来完成这项工作，这有点像重新发明轮子。 C++ STL 几乎总是包含一些可以让您的生活更轻松的东西，所以在您开始工作之前搜索它。

如果您正在编写一个更大的项目，请不要使用 using namespace，但对于像这样的小玩具来说没问题。

Answer 2

正如我在我的一个回答中所说的那样，在 C++ 中滚动您自己的容器通常会导致代码混乱且难以阅读，这在建模问题时毫无帮助。

在现代 C++ 中（即在 C++11 之后，现在理想情况下你应该使用 C++17，甚至开始胆怯地涉足 C++20）你几乎不需要像 operator new 这样的东西， NULL 并且通常根本没有指针（它们仍然可以用作缺少 std::optional<T&> 的权宜之计）。

顺便说一下，我认为不需要使用队列来解决你的问题；一个 "current item" 变量就足够了；然后，您可以通过在列表中搜索与当前元素的汉明距离为 1 的字符串来找到下一个元素。由于循环的可能性，它在一般情况下不起作用，但如果您只处理有限的单词列表（例如您的单词列表），而实际上只有一个可能的阶梯，这就足够了。

这就是我如何在 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;
}

输出为：

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

我使用 std::vector 而不是更“优化”的容器，因为它通常是最好的全能选择，即使在严重受限的系统上，由于现代 CPU 的速度有多快。链表特别糟糕，应该（几乎）总是避免，因为它们来自指针间接的大量开销，这抵消了您可能从中获得的任何理论收益。

一般来说，你应该默认使用vector和hashmaps（即std::unordered_map），只有当你确实需要它们时才考虑其他容器。

如何创建单词阶梯？

How do create a word ladder?

c++

queue

linked-list

算法

你犯的错误以及我如何修正它们：

文体建议