[Leetcode]Word Ladder

题目：

?

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

   For example,

   Given:
   start = "hit"
   end = "cog"
   dict = ["hot","dot","dog","lot","log"]

   As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
   return its length 5.

   Note:

   • Return 0 if there is no such transformation sequence.
   • All words have the same length.
   • All words contain only lowercase alphabetic characters.

     ?

     解题思路：采用BFS搜索。每个节点采用pair表示，每个pair的第一个元素是字符串本身，第二个元素是所在层次。

     ?

     代码：

     ?

     class Solution {
     public:
         int ladderLength(string start, string end, unordered_set
           
             &dict) {
             queue
            
             > WordCandidate; if(start.empty()||end.empty())return 0; int size=start.size(); if(start==end)return 1; WordCandidate.push(make_pair(start,1)); while(!WordCandidate.empty()){ pair
             
               CurrWord(WordCandidate.front()); WordCandidate.pop(); for(int i=0;i
              
               0){ WordCandidate.push(make_pair(CurrWord.first,CurrWord.second+1)); dict.erase(CurrWord.first); } swap(c,CurrWord.first[i]); } } } return 0; } };
              
             
            
           

     
     
     

     ?