Word Ladder

Leetcode

Problem Statement

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s_1 -> s_2 -> ... -> s_k such that:

  • Every adjacent pair of words differs by a single letter.
  • Every s_i for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • s_k == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Solution

class Solution { public: int getDiff(string a, string b) { int diff = 0; for (int i = 0; i < max(a.size(), b.size()); i++) { if (i < a.size() && i < b.size()) { if (a[i] != b[i]) diff++; } else { diff++; } } return diff; } int ladderLength(string beginWord, string endWord, vector<string>& wordList) { int n = wordList.size(); // vector<bool> seen(n, false); unordered_set<string> unusedWords; for (const auto s: wordList) { if (s != beginWord) unusedWords.insert(s); } vector<string> seq; queue<pair<string, int>> q; q.push({beginWord, 1}); while (!q.empty()) { auto t = q.front(); q.pop(); string a = t.first; int stage = t.second; // while (seq.size() >= stage) { // seq.pop_back(); // } // seq.push_back({ a }); vector<string> matchingWords; for (auto s: unusedWords) { if (getDiff(a, s) == 1) { if (s == endWord) { // for (auto p: seq) { // cout << p << "\n"; // } // cout << s << "\n"; return stage + 1; } else { matchingWords.push_back(s); } } } for (const string s: matchingWords) { q.push({s, stage + 1}); unusedWords.erase(s); } } return 0; } };
Home | © 2024 Last Updated: Mar 03, 2024
Buy Me A Coffee