[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;i0){
                             WordCandidate.push(make_pair(CurrWord.first,CurrWord.second+1));
                             dict.erase(CurrWord.first);
                         }
                         swap(c,CurrWord.first[i]);
                     }
                 }
             }
         return 0;
         }
     };