leetcode 126和127单词接龙相似写法

汇总了个人认为比较清晰的单词接龙的2道题目解法，127和126代码比较相似，以方便记忆。

参考思路：https://leetcode-cn.com/problems/word-ladder/solution/yan-du-you-xian-bian-li-shuang-xiang-yan-du-you-2/

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector& wordList) {
        unordered_set words(wordList.begin(), wordList.end());
        if ( words.empty() || words.find(endWord) == words.end() ) return 0;
        words.erase(beginWord);
        queue que;
        que.push(beginWord);
        //depth相当于树的层数
        int depth = 1;
        while ( !que.empty() ) {
            // 找到没有被访问过, 而且能够由当前单词转换而成的单词
            int n = que.size();
            //下一层的while结束表示树的深度+1
            while ( n-- ) {
                string curWord = que.front();
                que.pop();
                // 当前单词的每个字符都替换成其他的25个字符, 然后在单词表中查询
                for ( int i = 0; i < curWord.size(); ++i ) {
                    char originalChar = curWord[i];
                    for ( int j = 0; j < 26; ++j ) {
                        if ( char('a' + j) == originalChar ) continue;
                        curWord[i] = 'a' + j;
                        //如果单词表中存在且未被访问过
                        if ( words.find(curWord) != words.end()) {
                            if ( curWord == endWord ) return depth + 1;
                            else {
                                que.push(curWord);
                                //如果找到，则直接在字符表中删除
                                words.erase(curWord);
                            }
                        }
                    }
                    curWord[i] = originalChar;
                }
            }
            ++depth;
        }
        return 0;
    }
};

参考思路：评论区的@swjtulwy的解法

class Solution
{
public:
   vector> findLadders(string beginWord, string endWord, vector &wordList)
   {
      vector> res;
      unordered_set words{wordList.begin(), wordList.end()};
      unordered_set visited;
      queue> que;
      words.erase(beginWord);
      que.push({beginWord});
      while (!que.empty())
      {
         int n = que.size();
         while (n--)
         {
            vector curPath = que.front();
            que.pop();
            string curWord = curPath.back();
            for (int i = 0; i < curWord.size(); i++)
            {
               char originChar = curWord[i];
               for(char c='a';c<='z';c++)
               {
                  curWord[i]=c;
                  //替换后成功在单词表中找到
                  if(words.count(curWord)==1)
                  {
                     vector newPath=curPath;
                     newPath.push_back(curWord);
                     //标记该单词
                     visited.insert(curWord);
                     if(curWord!=endWord)
                     {
                        que.push(newPath);
                     }
                     else
                     {
                        res.push_back(newPath);
                     }
                  }
               }
               curWord[i]=originChar;
            }
         }
         for(auto &str:visited)
          words.erase(str);
      }
      return res;
   }
};