127. Word Ladder 词语阶梯

[GH1995]

127. Word Ladder

Difficulty: Medium

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

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.

Example 2:

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.

[GH1995]

这题很经典，看代码

图个表示和构造 用 map 构造邻接表表示的图，map 定义为以 string 为 key, vector<string> 为 value 将 beginWord push 进 wordList，遍历 wordList, 对任意两个单词 wordList[i] 和wordList[j] 如果只相差 1 个字符，则将其相连

[GH1995]

class Solution {
 public:
  int ladderLength(string beginWord, string endWord, vector<string> &wordList) {
    map<string, vector<string>> graph;
    construct_graph(beginWord, wordList, graph);
    return bfs(beginWord, endWord, graph);
  }
  // 图个表示和构造
  // 用 map 构造邻接表表示的图，map 定义为以 string 为 key, vector<string> 为
  // value
  // 将 beginWord push 进 wordList，遍历 wordList, 对任意两个单词 wordList[i] 和
  // wordList[j] 如果只相差 1 个字符，则将其相连
  bool connect(const string &word1, const string word2) {
    int cnt = 0;
    for (int i = 0; i < word1.size(); ++i)
      if (word1[i] != word2[i]) ++cnt;
    return cnt == 1;
  }
  void construct_graph(string &beginWord, vector<string> &wordList,
                       map<string, vector<string>> &graph) {
    wordList.push_back(beginWord);
    for (int i = 0; i < wordList.size(); ++i)  // 构建顶点
      graph[wordList[i]] = vector<string>();
    for (int i = 0; i < wordList.size(); ++i)  // 构建边，如此简单
      for (int j = i + 1; j < wordList.size(); ++j) {
        if (connect(wordList[i], wordList[j])) {
          graph[wordList[i]].push_back(wordList[j]);
          graph[wordList[j]].push_back(wordList[i]);
        }
      }
  }
  // BFS
  // 起点 beginWord, 终点 endWord
  // 搜索记录步数
  // Q 的节点为 pair<顶点, 步数>，设置集合 visit ，记录搜索过的顶点
  // 将 <beginWord, 1> 添加至队列
  // 若取出的头元素是 endWord，返回到达该顶点的步数
  // 不是的话，就添加相连的到 visit 中
  int bfs(const string &beginWord, const string &endWord,
          const map<string, vector<string>> &graph) {
    queue<pair<string, int>> q;
    set<string> visit;  // 标记被访问的节点
    q.push(make_pair(beginWord, 1));
    visit.insert(beginWord);
    while (!q.empty()) {
      auto node = q.front().first;
      auto step = q.front().second;
      q.pop();
      if (node == endWord)  // 临界条件
        return step;
      auto &neighbors = graph.at(node);
      for (auto &ng : neighbors) {
        if (visit.find(ng) == visit.end()) {
          q.push(make_pair(ng, step + 1));
          visit.insert(ng);
        }
      }
    }
    return 0;
  }
};