查找兩個給定詞和詞典之間的最短詞梯

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