PHP第五周答案,算法设计与分析第五周作业——Word Ladder
算法設(shè)計(jì)與分析第五周作業(yè)——Word Ladder
上周找了一道深度搜索優(yōu)先搜索的算法題來(lái)做，于是這周就選了一道廣度優(yōu)先搜索算法題來(lái)試試手。
本周所選題目：原題目鏈接
題目詳情
題目大意：給出一個(gè)字符串(單詞)集合和兩個(gè)字符串，一個(gè)為開(kāi)始字符串，一個(gè)為結(jié)束字符串，每次通過(guò)改變一個(gè)字符使得從開(kāi)始字符串依次轉(zhuǎn)變?yōu)樽址侠锏淖址?#xff0c;直到轉(zhuǎn)化為結(jié)束字符串，求所用到的最少的步數(shù)。
注：如果不存在這樣一條路徑，則返回0；
所有涉及到的字符串都是一樣大小的，且所有字母都為小寫；
字符串集合中無(wú)重復(fù)的字符串，開(kāi)始字符串和結(jié)束字符串非空。
樣例說(shuō)明：Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
題目分析和算法設(shè)計(jì)
很顯然，題目需要我們通過(guò)對(duì)每個(gè)單詞進(jìn)行廣搜以求得最短的路徑。可以構(gòu)建這樣的模型：以每個(gè)字符串為頂點(diǎn)，如果字符串集合中存在一個(gè)只需要當(dāng)前字符串修改一個(gè)字符就能達(dá)到的字符串，那么這兩個(gè)字符串之間就存在有一條邊，可以理解為邊的值為1。
根據(jù)已知條件，我們可知知道應(yīng)該使用的數(shù)據(jù)結(jié)構(gòu)為：set(無(wú)重復(fù)字符串)：字符串集合，用來(lái)未訪問(wèn)的存儲(chǔ)字符串；
queue：用來(lái)存儲(chǔ)當(dāng)前訪問(wèn)的字符串；
其中，queue使用鍵值對(duì)來(lái)進(jìn)行對(duì)步數(shù)的記錄，每一個(gè)值由(當(dāng)前字符串，步數(shù))的鍵值對(duì)組成。
具體算法：依次對(duì)當(dāng)前字符串的各個(gè)字符進(jìn)行變換，如果變換之后得到的字符串在字符串集合中，那么說(shuō)明是可以進(jìn)行轉(zhuǎn)換的，此時(shí)遞增步數(shù)，并把該字符串放入到隊(duì)列中，同時(shí)從字符串集合中移除，直至轉(zhuǎn)換到結(jié)束字符串，返回當(dāng)前的步數(shù)，即隊(duì)列值的數(shù)值。
代碼詳情class Solution {
public:
int ladderLength(string beginWord, string endWord, vector& wordVec) {
set wordList;
for (auto word : wordVec) {
wordList.insert(word);
}
if (wordList.find(endWord) == wordList.end()) return 0;
queue> que;
que.push(make_pair(beginWord, 1));
while(!que.empty()) {
auto val = que.front();
que.pop();
if(val.first == endWord) return val.second;
for(unsigned i = 0; i < val.first.size(); i++) {
string str = val.first;
for(char j = 'a'; j <= 'z'; j++) {
str[i] = j;
if(wordList.find(str) != wordList.end()) {
que.push(make_pair(str, val.second+1));
wordList.erase(str);
}
}
}
}
return 0;
}
};
上面的題目主要考察簡(jiǎn)單的廣度優(yōu)先搜索算法，是比較簡(jiǎn)單的。同時(shí)LeetCode上有一道Word Ladder II，雖然題目類似，Word Ladder II要求把具體的所有最短的路徑找出來(lái)作為返回值。下面我們來(lái)分析一下該題：
該題目大概思路跟Word Ladder是類似的，但是在細(xì)節(jié)方面是有更多需要考慮的。需要求字符串集合的集合，即具體的轉(zhuǎn)換路徑的集合，需要以下的數(shù)據(jù)結(jié)構(gòu)和變量：queue> paths：路徑集paths，用以保存所有路徑；
unordered_set dict：存未訪問(wèn)過(guò)的字符串，初始化為輸入的字符串集；
unordered_set words：記錄已經(jīng)循環(huán)過(guò)的路徑中的詞；
level：整型變量，記錄循環(huán)中當(dāng)前路徑的長(zhǎng)度；
minLevel：整型變量，記錄最短路徑的長(zhǎng)度；
算法過(guò)程：把起始路徑加入路徑集paths，當(dāng)paths非空時(shí)進(jìn)行循環(huán)，取隊(duì)列頭路徑，把路徑的最后一個(gè)達(dá)到的字符串拿出來(lái)進(jìn)行廣搜，即對(duì)每個(gè)字符，都從‘a(chǎn)’-‘z’進(jìn)行轉(zhuǎn)換，如果dict中有該中間轉(zhuǎn)換得到的字符串，說(shuō)明滿足條件可以進(jìn)行路徑的記錄，此時(shí)判斷該字符串是否為結(jié)束字符串，如果是，則找到一條路徑，否則把得到的新路徑加入paths中，繼續(xù)循環(huán)。需要注意的是如果paths里的路徑的長(zhǎng)度大于level，說(shuō)明字典中的有些詞已經(jīng)存入路徑了，如果在路徑中重復(fù)出現(xiàn)，則肯定不是最短路徑，所以我們需要在字典中將這些詞刪去，然后將words清空。
代碼詳情：class Solution {
public:
vector> findLadders(string beginWord, string endWord, vector& wordList) {
vector> res;
unordered_set dict(wordList.begin(), wordList.end());
vector p{beginWord};
queue> paths;
paths.push(p);
int level = 1, minLevel = INT_MAX;
unordered_set words;
while (!paths.empty()) {
auto t = paths.front();
paths.pop();
if (t.size() > level) {
for (string w : words) dict.erase(w);
words.clear();
level = t.size();
if (level > minLevel) break;
}
string last = t.back();
for (int i = 0; i < last.size(); ++i) {
string newLast = last;
for (char ch = 'a'; ch <= 'z'; ++ch) {
newLast[i] = ch;
if (!dict.count(newLast)) continue;
words.insert(newLast);
vector nextPath = t;
nextPath.push_back(newLast);
if (newLast == endWord) {
res.push_back(nextPath);
minLevel = level;
} else paths.push(nextPath);
}
}
}
return res;
}
};
謝謝閱讀。
參考資料：
總結(jié)
以上是生活随笔為你收集整理的PHP第五周答案,算法设计与分析第五周作业——Word Ladder的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： linux中oracle静默安装失败,o
- 下一篇： php js获取file,PHP fil