LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 用 set 保存单词的初始状态（from），不断更新 from 到下一状态，直到 from 中有单词能转换为目标单词

["hot", "dot", "dog", "lot", "log", "cog"]
["hit"]
["cog"]

第一次转换
["dot", "dog", "lot", "log", "cog"]
["hot"]
["cog"]

第二次转换
["dog", "log", "cog"]
["dot", "lot"]
["cog"]

第三次转换
["cog"]
["dog", "log"]
["cog"]

第四次转换
"dog" 可转为 "cog"，结束

"hit" => "hot" => "dot", "lot" => "dog", "log" => "cog"，长度为 5

• 要从一个单词转为另一个单词，对单词的每个字符做替换即可

hit => *it => * 为 a-z
hit => h*t => * 为 a-z
hit => hi* => * 为 a-z

共26 * 3 = 78 个单词，找出所有在字典中的，仅有 hot
因此 ["hit"] 可转换为 ["hot"]，转换结束后从字典删去已用过的状态

• 解法如下

class Solution {
 public:
  int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> wordSet{begin(wordList), end(wordList)};
    if (!wordSet.count(endWord)) {
      return 0;
    }
    unordered_set<string> from{beginWord};
    int res = 1;
    while (!empty(from)) {
      ++res;
      unordered_set<string> t;  // 保存from的下一次状态
      for (auto& x : from) {
        wordSet.erase(x);  // 删除已有状态
      }
      for (auto& x : from) {  // 对 from 中的每个单词做字符替换
        for (int i = 0; i < size(x); ++i) {
          string s = x;
          for (char c = 'a'; c <= 'z'; ++c) {
            s[i] = c;
            if (wordSet.count(s)) {  // 如果替换后的字符在字典中
              if (s == endWord) {
                return res;
              }
              t.emplace(s);
            }
          }
        }
      }
      from = t;  // 更新当前状态为下一状态
    }
    return 0;
  }
};

• 每次都要遍历 from 的所有单词，这个过程可以进行优化。用另一个 set 保存单词的终止状态（to），只要 from 能有单词转换为 to 中的单词即可，反之亦然。如果 to 的单词少，则交换 from 和 to，从而实现从 to 向 from 转换

["hot", "dot", "dog", "lot", "log", "cog"]
["hit"]
["cog"]

第一次转换
["dot", "dog", "lot", "log", "cog"]
["hot"]
["cog"]

第二次转换，to单词更少，交换from和to
["dot", "dog", "lot", "log"]
["cog"]
["dot", "lot"]

第三次转换
["dot", "lot"]
["dog", "log"]
["dot", "lot"]

第四次转换
"dog" 可转为 "dot"，结束

"hit" => "hot" => "dot", "lot" <= "dog", "log" <= "cog"，长度为 5

• 解法如下

class Solution {
 public:
  int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> wordSet{begin(wordList), end(wordList)};
    if (!wordSet.count(endWord)) {
      return 0;
    }
    unordered_set<string> from{beginWord};
    unordered_set<string> to{endWord};
    int res = 1;
    while (!empty(from)) {
      ++res;
      unordered_set<string> t;
      for (auto& x : from) {
        wordSet.erase(x);
      }
      for (auto& x : from) {
        for (int i = 0; i < size(x); ++i) {
          string s = x;
          for (char c = 'a'; c <= 'z'; ++c) {
            s[i] = c;
            if (wordSet.count(s)) {
              if (to.count(s)) {
                return res;
              }
              t.emplace(s);
            }
          }
        }
      }
      if (size(t) > size(to)) {
        from = to;
        to = t;
      } else {
        from = t;
      }
    }
    return 0;
  }
};