單向bfs 方法也是想到和寫了出來，就是沒有用find這個方法導致超時！！！用了iterator 其實就是bfs不斷判斷是否是那就ok了，數據結構的使用方法還是有點弱！
class Solution {public: void addnext(string s, queue<string>& qu, unordered_set<string>& WordList){ wordList.erase(s); for(int i = 0; i < s.length(); ++ i){ char temp = s[i]; for(int j = 0; j < 26; ++ j){ s[i] = 'a' + j; if(wordList.find(s) != wordList.end()){ qu.push(s); wordList.erase(s); } } s[i] = temp; } } int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) { wordList.insert(endWord); queue<string>qu; addnext(beginWord, qu, wordList); int sum = 2; while(!qu.empty()){ int n = qu.size(); for(int i = 1; i <= n; ++ i){ string t = qu.front(); qu.pop(); if(t == endWord) return sum; addnext(t, qu, wordList); } sum++; } return 0; }};雙向bfs 雙向bfs，比單向更快，沒有用queue，用了unorder set一樣可以做，每次結束就裝換，開兩個，一頭一尾，這題十分考驗打碼能力，非思維能力，2刷值得繼續練習！
class Solution {public: int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) { unordered_set<string> head, tail, *phead, *ptail; head.insert(beginWord); tail.insert(endWord); int sum = 2; while(!head.empty() && !tail.empty()){ if(head.size() < tail.size()){ phead = &head; ptail = &tail; } else{ phead = &tail; ptail = &head; } unordered_set<string> temp; for(auto it = phead -> begin(); it != phead -> end(); it++){ string word = *it; wordList.erase(word); for(int i = 0; i < word.length(); ++ i){ char t = word[i]; for(int j = 0; j < 26; ++ j){ word[i] = 'a' + j; if(ptail -> find(word) != ptail -> end()) return sum; if(wordList.find(word) != wordList.end()){ temp.insert(word); wordList.erase(word); } } word[i] = t; } } sum++; swap(*phead, temp); } return 0; }};新聞熱點
疑難解答
