BFS广度优先

752. 打开转盘锁

方法一：BFS

class Solution {
public:
    string plusOne(string s,int i){
        if(s[i] == '9')s[i] = '0';
        else s[i] = s[i] + 1;
        return s;
    }
    string minusOne(string s,int i){
        if(s[i] == '0')s[i] = '9';
        else s[i] = s[i] - 1;
        return s;
    }
    set<string>visited;
    int openLock(vector<string>& deadends, string target) {
        queue<string>q;
        q.push("0000");
        visited.insert("0000");
        for(auto&s : deadends){
            if(s == "0000")return -1;
            visited.insert(s);
        }
        int step = 0;
        while(!q.empty()){
            int size = q.size();
            
            //当前队列的所有节点判断
            while(size--){
                string cur = q.front();
                q.pop();
                
                //找到目标值那么返回
                if(cur == target)return step;
                
                //对当前节点的所有邻接节点加入队列
                for(int i = 0;i < 4;i++){
                    string up = plusOne(cur, i);
                    string down = minusOne(cur, i);
                    if(visited.find(up) == visited.end()){
                        q.push(up);
                        visited.insert(up);
                    }
                    if(visited.find(down) == visited.end()){
                        q.push(down);
                        visited.insert(down);
                    }  
                }
            }
            //这里增加步数
            step++;
        }
        return -1;
    }
};

方法二：双向BFS

传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。

双向 BFS 也有局限，因为你必须知道终点在哪里。

双向 BFS 还是遵循 BFS 算法框架的，只是不再使用队列，而是使用 set 方便快速判断两个集合是否有交集。
另外的一个技巧点就是 while 循环的最后交换 q1 和 q2 的内容，所以只要默认扩散 q1 就相当于轮流扩散 q1 和 q2。
其实双向 BFS 还有一个优化，就是在 while 循环开始时做一个判断：

class Solution {
public:
    string plusOne(string s,int i){
        if(s[i] == '9')s[i] = '0';
        else s[i] = s[i] + 1;
        return s;
    }
    string minusOne(string s,int i){
        if(s[i] == '0')s[i] = '9';
        else s[i] = s[i] - 1;
        return s;
    }
    set<string>visited;
    int openLock(vector<string>& deadends, string target) {
        set<string>s1;
        s1.insert("0000");
        visited.insert("0000");
        for(auto&s : deadends){
            if(s == "0000")return -1;
            visited.insert(s);
        }
        set<string>s2;
        s2.insert(target);
        int step = 0;

        while(!s1.empty() && !s2.empty()){
            set<string>temp;
            //set1的节点扩散,while(size--)修改为for范围查找
            for(auto cur : s1){
                //找到了目标值，可以放回了
                if(s2.find(cur) != s2.end())return step;
                //这里标记为已经访问过
                visited.insert(cur);
                //节点扩散
                for(int i = 0;i < 4;i++){
                    string up = plusOne(cur, i);
                    string down = minusOne(cur, i);
                    if(visited.find(up) == visited.end())temp.insert(up);
                    if(visited.find(down) == visited.end())temp.insert(down);
                }
            }
            //增加步数，并且修改s1和s2
            step++;
            s1 = s2;
            s2 = temp;
        }   

        return -1;
    }
};

127. 单词接龙

class Solution {
public:
    bool check(string s,string t){
        int len = s.length();
        int cnt = 0;
        for(int i = 0;i < len;i++){
            if(s[i] != t[i])cnt++;
        }
        return cnt == 1;
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if(wordSet.find(endWord) == wordSet.end())return 0;
        unordered_set<string>s1;s1.insert(beginWord);
        unordered_set<string>s2;s2.insert(endWord);
        unordered_set<string>visited;

        int step = 1;
        while(!s1.empty()&&!s2.empty()){
            
            if (s1.size() > s2.size()) {
                swap(s1,s2);
            }
            unordered_set<string>temp;
            for(auto cur : s1){
                //判断是否到终点
                if(s2.find(cur)!=s2.end())return step;
                //当前节点加入已经访问队列
                visited.insert(cur);
                //cur邻接节点加入队列
                for(auto word : wordList){
                    if(check(word, cur) && visited.find(word) == visited.end()){
                        temp.insert(word);
                    }
                }
            }
            step++;
            s1 = s2;
            s2 = temp;
        }
        return 0;
    }
};