题解 | #词语序列#

class Solution {
public:
  int ladderLength(string start, string end, unordered_set<string> &dict) {
    if (!dict.count(end)) return 0;

    queue<string> q{{start}};
    unordered_set<string> seen{start};

    int steps = 0;
    while (not q.empty()) {
      size_t s = q.size();
      while (s--) {
        const auto curr = q.front(); q.pop();
        if (curr == end) return steps + 1;
        for (int i = 0; i < curr.length(); ++i) {
          string nxt(curr);
          const char c = curr[i];
          for (char j = 'a'; j <= 'z'; ++j) {
            if (j == c) continue;
            nxt[i] = j; 
            if (seen.count(nxt) || !dict.count(nxt)) continue;
            q.emplace(nxt);
            seen.emplace(nxt);
          }
        }
      }
      ++steps;
    }

    return 0;
  }
};