查找两个给定词和词典之间的最短词梯

Question

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

我试图用BFS解决这个问题;通过查找字典中的下一个单词并检查它是否与队列中弹出的项目相邻。尽管如此，这种方法不会给我最短的路径：

如果我尝试用26个字母替换每个字母，并且结果词出现在词典中，请接受：仍然这种方法不会给我最短的路径。例如：在这里，它应该给我：hit-> lit-> lot-> hot-> hol-> lil-> cil

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

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

Answer 1

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

如果目标单词等于开始单词，或者具有Levenshtein distance 1结果为[start, target]并且您完成了。

否则，您必须从开始单词中找到Levenshtein距离为1的字典的所有成员。如果其中一个Levenshtein与目标词的距离为1，则结果为[start, word, target]，您就完成了。否则，您将所选列表中的每个单词作为开始，并将目标作为目标，并将start预设为最短结果。

伪码 - 有点儿蟒蛇像：

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的字段的路。如果回溯将我们带回到右下单元格，则没有解决方案。

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

目前我没有时间思考。如果证明这不是一个完整的解决方案，则可以将其用作优化步骤而不是shortestWOrdLadder()第一行中的levenshtein(start, target)呼叫，因为该算法为您提供了Levenshtein距离以及可能的最短路径。

Answer 2

我建议在词典中的单词上建立一个图表，其中一个节点表示一个单词，并且存在从<→b的边，如果b可以通过更改a中的一个字符（当然，反之亦然）。该过程将花费O（n * n）时间，其中n是否。词典中的单词。
如何做到这一点如下：
对于每个单词构建频率数组的字符，称它为farr，长度为26，farr [i]表示字母i按字母顺序出现在单词中的次数，以及然后在一个运行n * n次的嵌套循环中，您只需比较单词的频率表条目，它们必须相差仅一个字符才能具有从单词a到b的边。
另请注意，此图中的边缘是无向的（在两个方向上）。
在建立词典单词的完整图形后，还可以将问题单词添加到图表中。然后继续BFS从初始单词的节点搜索目标单词，其中所需的转换是初始单词 - >目标单词。 现在说你在'i'级找到目标单词，而从最初的单词探索，然后最短的路径是'我'单位长。

Answer 3

我已经通过采用以下方法制定了解决方案： 1.）我先从字典中构建了一棵树，假设起点是给定的单词;并找到与该单词相邻的所有单词等等。 2.）接下来，我尝试使用此树构建从给定单词到结束单词的所有可能路径。复数：O（n * 70 + 2^n-1 * lg（n））= O（2^n-1 * lg（n））这里n是词典中的词数，70来作为从65到122（A到a）的ASCII值的范围，我在这里已经取得了一个圆整的数字。复杂性如预期的那样呈指数级增长。即使在某些优化之后，最坏情况的复杂度也不会改变。

这里是我写的代码（其由我测试和工程的任何错误或建议，将不胜感激。）：

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