Simple to understand C++ solution


  • 0
    B
    bool good(const string& w1, const string& w2) {
      int diff = 0;
      for (int i = 0; i < w1.size(); ++i) {
        if (w1[i] != w2[i]) diff++;
        if (diff > 1) return false;
      }
    
      return diff == 1;
    }
    
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
      queue<string> q;
      unordered_set<string> wl(wordList.begin(), wordList.end());
      q.push(beginWord);
    
      int len = 1;
    
      while (!q.empty()) {
        int n = q.size();
        for (int i = 0; i < n; ++i) {
          auto curr = q.front();
          if (curr == endWord) return len;
          q.pop();
          wl.erase(curr);
          
          auto it = wl.begin();
          while (it != wl.end()) {
            if (good(curr, *it)) {
                q.push(*it);
                it = wl.erase(it);
            } else {
                ++it;
            }
          }
        }
        len++;
      }
    
      return 0;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.