最短費用字轉換

Question

我想解決以下問題。

給你一個開始詞，詞典和結束詞。您可以執行4個操作。

1. 在任何位置
2. 刪除字母添加一個字母在任何位置
3. 在任何位置替換字母的單詞的
4. 採取字謎（貓是可以改變的行動）。

這些操作的所有成本可能會有所不同，並且也會給出。

約束：所有中間字母以及開始詞和結束詞必須出現在詞典中。找到實現這一目標的最低可能成本。

如果沒有辦法返回-1;

有什麼想法嗎？

Answer 1

我想你應該告訴我更多關於約束的細節（如單詞的最大長度或字典中單詞的最大數量）。

但我會告訴你一個解決方案來解決這個問題。

首先，您可以製作圖表。每個節點都是您可以製作的單詞（在字典中），邊是您可以執行的操作。

每條邊都有從輸入給出的權重。那麼你應該保存從開始詞到詞典中其他每個詞的距離。在C++中，你可以聲明map<string, int>。

該地圖的關鍵是節點字符串，該地圖的值是距離初始單詞的距離。

然後，您可以使用像dijkstra這樣的最短距離算法。起點是首字，結束點是我們想要做的一個詞。因爲Dijkstra是通常只有一個起點的最快算法，如果我是你，我會使用它。

然後，我們來計算時間複雜度。

讓我們說每一個字的最大長度爲S，在字典中的單詞的最大數量爲N.

在每一個操作，它需要O（S），如果你改變一些字符位置或添加或刪除除了單詞後面的某個位置的字符和O（1）如果你只是改變一個字符。

總而言之，時間複雜度爲O（SNlgN）cuz圖中最大節點數是詞典cuz中單詞的最大數量，如果在字典中有任何單詞，我們可以從現在的單詞中做出，那麼我們不能再從當前節點創建邊緣。

最大邊數爲O（N）cuz，我們最多可以在每個節點做4個邊。所以如果你知道Dijkstra堆的時間複雜性，那很簡單。

Answer 2

我想你應該告訴我更多關於約束的細節（如單詞的最大長度或字典中單詞的最大數量）。 但我會告訴你一些解決這個問題的方法。 首先，你可以製作圖表。每個節點都是您可以製作的單詞（在字典中），邊是您可以執行的操作。每個邊都有從輸入中給出的權重。在C++中，您可以聲明地圖<string, int>。該地圖的關鍵是節點字符串，該地圖的值是與初始單詞的距離。 然後你可以使用像dijkstra這樣的最短距離算法。因爲Dijkstra是通常只有一個起點的最快算法，如果我是你，我會使用它。然後，我們來計算時間複雜度。假設每個單詞的最大長度是S，並且字典中的單詞的最大數量是N.在每個操作中，如果您可能會更改某些角色的位置或在某個位置添加或移除某個角色（除了背面），則需要O（S）的字