LeetCode-双路BFS_leetcode 双向bfs

1 开密码锁

剑指 Offer II 109. 开密码锁

752. 打开转盘锁

class Solution {
public:
	int openLock(vector<string>& deadends, string target) {
		//记录需要跳过的死亡密码
		unordered_set<string> deads(deadends.begin(), deadends.end());
 
		//记录已经穷举过的密码,防止走回头路
		unordered_set<string> visited;
		//用集合而不用队列,可以快速判断元素是否存在
		unordered_set<string> s1, s2;
 
		//从起点开始启动广度优先搜索
		int step = 0;
		s1.insert("0000");
		s2.insert(target);
 
		while (!s1.empty() && !s2.empty())
		{
            //保证从节点较小的那个集合开始广度遍历，这里固定从s1开始
            if (s2.size() < s1.size())         
            {
                s1.swap(s2);
            }
			//哈希集合在遍历过程中不能修改,故此处用temp来存储扩散结果
			unordered_set<string> temp;
			//将当前队列中的所有节点向周围扩散
            for (auto& cur : s1)
            {
				//判断是否到达终点
				if (deads.count(cur))
				{
					continue;
				}
                //如果本次遍历的邻居就是目标节点，则找到一条从起始到目标节点的最短路径
				if (s2.count(cur))
				{
					return step;
				}
 
				visited.insert(cur);
				//将一个节点的未遍历的相邻节点加入到队列中
				for (int j = 0; j < 4; ++j)
				{
					string up = plusOne(cur, j);
					if (!visited.count(up))
					{
						temp.insert(up);
					}
 
					string down = minusOne(cur, j);
					if (!visited.count(down))
					{
						temp.insert(down);
					}
				}
            }
 
			//在这里增加步数
			++step;
            s1.swap(temp);
		}
 
		//如果穷举完都没有找到目标密码,则返回-1
		return -1;
	}
 
	string plusOne(const string& s, int j)
	{
		string tmp(s);
		if (tmp[j] == '9')
		{
			tmp[j] = '0';
		}
		else
		{
			tmp[j] += 1;
		}
 
		return tmp;
	}
 
	string minusOne(const string& s, int j)
	{
		string tmp(s);
		if (tmp[j] == '0')
		{
			tmp[j] = '9';
		}
		else
		{
			tmp[j] -= 1;
		}
 
		return tmp;
	}
};

2 单词接龙

127. 单词接龙

剑指 Offer II 108. 单词演变

//双向BFS
class Solution {
public:    
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // 如果目标单词不在 wordList 中，说明无解
        if (std::find(wordList.begin(), wordList.end(), endWord) == wordList.end())
            return 0;
 
        // 将所有 word 存入 unordered_set
        unordered_set<string> s;
        for (auto& str : wordList) 
            s.insert(str);
 
        int ans = bfs(beginWord, endWord, s);
        return ans == -1 ? 0 : ans + 1;
    }
 
    int bfs(const string& beginWord, const string& endWord, unordered_set<string>& s) 
    {
        // q1 代表从起点 beginWord 开始搜索（正向）
        // q2 代表从结尾 endWord 开始搜索（反向）
        queue<string> q1, q2;
        
        /*
         * m1 和 m2 分别记录两个方向出现的单词是经过多少次转换而来
         * e.g. 
         * m1 = {"abc":1} 代表 abc 由 beginWord 替换 1 次字符而来
         * m2 = {"xyz":3} 代表 xyz 由 endWord 替换 3 次字符而来
         */
        unordered_map<string, int> m1, m2;
		q1.push(beginWord); m1.insert({ beginWord, 0 });
		q2.push(endWord); m2.insert({ endWord, 0 });
        
        /*
         * 只有两个队列都不空，才有必要继续往下搜索
         * 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
         * e.g. 
         * 例如，如果 q1 为空了，说明从 beginWord 搜索到底都搜索不到 endWord，反向搜索也没必要进行了
         */
        while (!q1.empty() && !q2.empty()) 
        {
            int t = -1;
            // 为了让两个方向的搜索尽可能平均，优先拓展队列内元素少的方向
            if (q1.size() <= q2.size()) 
            {
                t = update(q1, m1, m2, s);
            } 
            else 
            {
                t = update(q2, m2, m1, s);
            }
 
            if (t != -1) 
                return t;
        }
 
        return -1;
    }
 
    // update 代表从 queue 中取出一个单词进行扩展，
    // cur 为当前方向的距离字典；other 为另外一个方向的距离字典
    int update(queue<string>& queue, unordered_map<string, int>& cur, unordered_map<string, int>& other, unordered_set<string>& s) 
    {
        int m = queue.size();
        while (m--) 
        {
            // 获取当前需要扩展的原字符串
            string firstStr = queue.front();
            queue.pop();
 
            // 枚举替换原字符串中索引为i的字符
            for (int i = 0; i < firstStr.length(); ++i) 
            {
                // 枚举将 i 替换成小写字母
                for (int j = 0; j < 26; ++j) 
                {
                    // 替换后的字符串
                    string nextStr = firstStr.substr(0, i).append(1, 'a'+j).append(firstStr.substr(i+1));
                    if (s.count(nextStr)) 
                    {
                        // 如果 nextStr 在「当前方向」被记录过，且被记录的次数小于等于 cur[firstStr] + 1, 加1表示 firstStr -> nextStr
                        if (cur.count(nextStr) && cur[nextStr] <= cur[firstStr] + 1) 
                            continue;
 
                        // 如果该字符串在「另一方向」出现过，说明找到了联通两个方向的最短路
                        if (other.count(nextStr)) 
                        {
                            return cur[firstStr] + 1 + other[nextStr];
                        } 
                        else 
                        {
                            // 否则加入 queue 队列
                            queue.push(nextStr);
                            cur.insert({nextStr, cur[firstStr]+1});
                        }
                    }
                }
            }
        }
 
        return -1;
    }
};

3

4