找到两个给定单词和一本词典之间的最短单词阶梯

Question

我试图从字典中找到两个给定单词之间的最短梯子。所有单词，包括给定的单词和字典中的单词都具有相同的字符数。在一次传递中，只能更改一个字符，并且需要最短路径。例如：给定：“命中”和“cil” Dic：[“hil”，“hol”，“hot”，“lot”，“lit”，“lil”] 所以，答案应该是“命中”-

我已经尝试使用BFS解决这个问题；通过在字典中找到下一个单词并检查它是否与队列中弹出的项目相邻。不过，这种方法不会给我最短路径：

如果，我试图用26个字母替换每个字母，并且如果字典中出现了生成的单词，请接受这一点：这种方法仍然不会给我最短的路径。例：这里，它会给我：一击-

也许，更好的方法是先构造一棵树，然后在树中找到从起始单词到结束单词的最短路径。

我知道，这个论坛上有这个问题的解决方案，但没有一个解释算法。我是BFS的新手，所以不太熟悉。我有兴趣知道如何找到最短路径之一，如果有几个，那么所有最短路径。

Answer 1

我通过采用以下方法找到了一个解决方案：1）我首先从字典中建立了一棵树，假设起点是给定的单词；然后，我尝试使用这棵树构建从给定单词到结束单词的所有可能路径。

复杂度：O（n*70 2^n-1 * lg（n）） = O（2^n-1*lg（n）） 这里 n 是字典中的单词数，70 是 ASCII 值的范围，从 65 到 122（A 到 a），我在这里取了一个整数。正如预期的那样，复杂性呈指数级增长。即使经过某些优化，最坏情况的复杂性也不会改变。

这是我写的代码（它由我测试并有效。任何错误或建议将不胜感激。

#include <iostream>
#include <vector>
#include <cstring>
#include <deque>
#include <stack>
#include <algorithm>

using namespace std;

struct node {
    string str;
    vector<node *> children;
    node(string s) {
        str = s;
        children.clear();
    }
};

bool isAdjacent(string s1, string s2) {
    int table1[70], table2 [70];
    int ct = 0;

    for (int i = 0; i < 70; i++) {
        table1[i] = 0;
        table2[i] = 0;
    }
    for (int i = 0; i < s1.length(); i++) {
        table1[((int)s1[i])- 65] += 1;
        table2[((int)s2[i])- 65] += 1;
     }

     for (int i = 0; i < 70; i++) {
        if (table1[i] != table2[i])
            ct++;
        if (ct > 2)
            return false;
     }
     if (ct == 2)
        return true;
     else
        return false;
}

void construct_tree(node *root, vector<string> dict) {
    deque<node *> q;
    q.push_back(root);
    while (!q.empty()) {
        node *curr = q.front();
        q.pop_front();
        if (dict.size() == 0)
            return;
        for (int i = 0; i < dict.size(); i++) {
            if (isAdjacent(dict[i], curr->str)) {
                string n = dict[i];
                dict.erase(dict.begin()+i);
                i--;
                node *nnode = new node(n);
                q.push_back(nnode);
                curr->children.push_back(nnode);
            }
        }
    }
}

void construct_ladders(stack<node *> st, string e, vector<vector <string> > &ladders) {
    node *top = st.top();
    if (isAdjacent(top->str,e)) {
        stack<node *> t = st;
        vector<string> n;
        while (!t.empty()) {
            n.push_back(t.top()->str);
            t.pop();
        }
        ladders.push_back(n);
    }
    for (int i = 0; i < top->children.size(); i++) {
        st.push(top->children[i]);
        construct_ladders(st,e,ladders);
        st.pop();
    }
}

void print(string s, string e, vector<vector<string> > ladders) {
    for (int i = 0; i < ladders.size(); i++) {
        for (int j = ladders[i].size()-1; j >= 0; j--) {
            cout<<ladders[i][j]<<" ";
        }
        cout<<e<<endl;
    }
}

int main() {
    vector<string> dict;
    string s = "hit";
    string e = "cog";

    dict.push_back("hot");
    dict.push_back("dot");
    dict.push_back("dog");
    dict.push_back("lot");
    dict.push_back("log");

    node *root = new node(s);
    stack<node *> st;
    st.push(root);

    construct_tree(root, dict);

    vector<vector<string> > ladders;
    construct_ladders(st, e, ladders);

    print(s,e,ladders);

    return 0;
}

Answer 2

这种方法有点蛮力，但可能是一个很好的起点。

如果目标单词等于起始单词，或者距离为1，则结果为< code>[start，target]，这样就完成了。

否则，您必须查找词典中与起始单词距离为1的所有成员。如果其中一个单词与目标单词的距离为1，那么结果是[start，word，target]，就完成了。否则，您将以所选列表中的每个单词作为开始，以目标作为目标，并将start前置到最短的结果。

伪代码 - 有点像python：

myDict = {"hil", "hol", "hot", "lot", "lit", "lil"}

used_wordlist = {}

shortestWordLadder(start, target):
    if start == target or levenshtein(start, target) = 1:
        return [start, target]

    current_wordlist = [x for x in myDict
                              if x not in used_wordlist and
                              levenshtein(ladder[-1], x) = 1]

    if current_wordlist.size = 0:
        return null

    for word in current_wordlist:
        if levenshtein(word, target) == 1:
            return [start, word, target]

     used_wordlist.insert_all(current_wordlist)
     min_ladder_size = MAX_INT
     min_ladder = null

     for word in currrent_wordlist:
         ladder = shortestWordLadder(word, target)

         if ladder is not null and ladder.size < min_ladder_size:
             min_ladder_size = ladder.size
             min_ladder = ladder.prepend(start)

     return min_ladder

可能的优化：

我考虑重用矩阵，levenshtein（start， Target）将在内部创建，但我无法获得足够的信心，它可以在所有情况下工作。这个想法是从矩阵的右下角开始，选择最小的邻居，这将从字典中创建一个单词。然后继续这个位置。如果当前单元格的邻居没有从字典中创建一个单词，我们必须回溯，直到找到一个值为0的字段。如果回溯将我们带回右下角单元格，则没有解决方案。

我现在不确定，可能没有解决方案，你可能会忽略这种方式。如果它找到解决方案，我很有信心，它是最短的之一。

目前我没有时间考虑清楚。如果证明这不是一个完整的解决方案，您可以将它用作一个优化步骤，而不是< code > shortestworldladder()的第一行中的< code>levenshtein(start，target)调用，因为该算法会为您提供levenshtein距离，如果可能的话，还会提供最短路径。

Answer 3

我建议在字典中的单词上构建一个图，其中一个节点表示一个单词