[数据结构与算法]LeetCode——126. 单词接龙 II

概述

题目地址

• 题目不难理解，这里不需要额外解释

思路

• 首先 题目要求寻找最短转换序列，那么我们容易想到使用BFS

  BFS思路这里不再介绍

• 沿着BFS考虑代码编写，问题在于如何正确保存获取目标单词的路径，有以下问题：
  • BFS利用队列，每次遍历一个level，获得的是每层可以访问的结点，并不是我们需要的路径
• 所以，BFS每次获得合法结点时，应该保存该结点及到达该结点的路径（即之前访问的结点序列）
  • 但是注意的是，BFS每次遍历一层，可能会导致有多条路径出现
  • 那么在遍历下一层时，应该对上一层产生的每条路径都需要分析才行

分析

• 如何确定结点访问的下一个合法结点？
  • 一种思路是通过遍历wordlist，比较和结点之间的差异，如果只有一字母不想同，则是合法结点
  • 令一种思路是从原结点出发，遍历它的所有可以通过一位变化产生的单词，判断是否在wordlist;
    如果在的话，则是合法结点

    实际上，根据数据限制，单词表最多有5000个，而单词长度5*26=100，所以第2种时间更少
    当然，为了加速判断操作，可以选择哈希表来保存原wordlist

• 如何保存每次路径？
  • 因为每层访问可能产生多条路径，所以选择以下数据结构保存路径

  queue<vector<string> path;
  

代码

class Solution {
public:

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

        vector<vector<string>> last_res;        // 保存最终结果

        unordered_map<string,int> search;       // 哈希保存wordlist
        for(auto s : wordList)
            search[s] = 1;

        queue<vector<string>> res;      // 保存每层遍历后产生的队列
        res.push({beginWord});          // 开始只有一条队列，从beginword开始

        int found = 0;      // 只要在某层找到endword,就不需进行后面的层查找

        while(!res.empty()) {

            int size_path = res.size();                 // 有几条路径
            unordered_set<string> visited_temp;     // 记录当前层的访问结点

            for (int i = size_path; i > 0; --i) {       // 每条结点都要访问下层结点
                auto path = res.front(); res.pop();     // 取出一条路径
                string path_last = path.back();         // 路径最后一个结点

                // 对该路径向下探索
                for (int j = 0; j < path_last.size(); ++j) {
                    char temp = path_last[j];
                    for (char c = 'a'; c <= 'z'; ++c){
                        if (temp == c)  continue;       // 自己本身跳过
                        path_last[j] = c;

                        if (!search[path_last])   continue; 	// 如果该结点之前访问过，也跳过

                        visited_temp.emplace(path_last);        // 保存该层访问过结点
                        // 这里注意，同一层是可以访问相同结点的，因为路径不同
                        // 所以，在同一层访问结点时，不能直接将访问的结点加入search

                        path.push_back(path_last);      // 保存最新的路径
                        if(path_last == endWord){       // 如果找到endword
                            found = 1;						// 记录
                            last_res.push_back(path);      // 将路径加入结果
                        } else 
                            res.push(path);

                        path.pop_back();        // 回溯
                    }
                    path_last[j] = temp;        // 回溯path_last,继续找下个合法结点
                }
            } 
            for (auto &p : visited_temp)       // 将该层所有访问的结点加入
                search[p] = 0;
            if (found) break;
        }  
        return last_res;
    }
};