資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++ 詞梯
假設我們有兩個單詞（beginWord 和 endWord），以及詞典的單詞列表，找出從 beginWord 到 endWord 的最短轉換序列的長度，條件是：
每次只能轉換一個字母。
每個轉換後的單詞必須存在於單詞列表中。beginWord 不是轉換後的單詞。
我們需要記住：
如果沒有這樣的轉換序列，則返回 0。
所有單詞長度相同。
所有單詞僅包含小寫字母。
我們可以假設單詞列表中沒有重複。
因此，如果輸入如下：beginWord = "hit"，endWord = "cog"，wordlist = ["hot", "dot", "dog", "lot", "log", "cog"]
則輸出將為 5，因為其中一個最短的轉換是 hit → hot → dot → dog → cog
為了解決這個問題，我們將遵循以下步驟：
定義一個名為 putStar 的方法，它將接收 j 和字串 s。其工作原理如下：
temp := 空字串
對於 i 的範圍為 0 到 s 的大小 – 1
如果 i = j，則透過將“*”與它連線來更新 temp，否則透過將 s[i] 與 temp 連線來更新 temp。
在主方法中，它將接收字串 b、字串 e 和單詞列表 w，其工作方式如下：
如果 e 不在 w 中，或者 b 為空，或者 e 為空，或者 w 為空，則返回 0
為字串型別鍵和陣列型別值定義一個對映 m。
對於 i 的範圍為 0 到 w 的大小
x := w[i]
對於 j := 0 到 x 的大小
inter := putStar(j, x)
將 x 插入 m[inter]
定義一個佇列 q，將一個對 (b, 1) 插入 q
建立一個名為 visited 的對映
當 q 不為空時
s := 來自 q 的前面一對，從 q 中刪除前面元素
x := 對 s 的第一個元素，l := 對 s 的第二個元素
對於 i 的範圍為 0 到 x 的大小
temp := putStar(i, x)
對於 j 的範圍為 0 到 m[temp] 的大小
aa := m[temp, j]
如果 aa 與 e 相同，則返回 l + 1
如果未設定 visited[aa]，則插入對 (aa, l + 1)，並設定 visited[aa] = 1
level := 0
返回 0
示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string putStar(int j, string s){
string temp = "";
for(int i = 0; i < s.size(); i++){
if(i == j)temp += "*";
else temp += s[i];
}
return temp;
}
int ladderLength(string b, string e, vector<string>& w) {
if(find(w.begin(), w.end(), e) == w.end() || !b.size() || !e.size() || !w.size())return 0;
map < string , vector <string> > m;
for(int i = 0; i < w.size(); i++){
string x = w[i];
for(int j = 0; j < x.size(); j++){
string inter = putStar(j,x);
m[inter].push_back(x);
}
}
queue < pair <string, int> > q;
q.push({b, 1});
map <string, int> visited;
while(!q.empty()){
pair < string, int > s = q.front();
q.pop();
string x = s.first;
int l = s.second;
for(int i = 0; i < x.size(); i++){
string temp = putStar(i ,x);
for(int j = 0; j < m[temp].size(); j++){
string aa = m[temp][j];
if(aa == e)return l+1;
if(!visited[aa]){
q.push({aa, l+1});
visited[aa] = 1;
}
}
}
}
int level = 0;
return 0;
}
};
main(){
vector<string> v = {"hot","dot","dog","lot","log","cog"};
Solution ob;
cout << (ob.ladderLength("hit", "cog", v));
}輸入
"hit" "cog" ["hot","dot","dog","lot","log","cog"]
輸出
5
752 次瀏覽
