leetcode-WordLadder

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.
     
     此题是图的遍历问题，要找一条起始点到目标点最短的路径，如果存在这样的路径则返回路径长度，否则返回0。 刚开始想到用深度优先搜索遍历，但是时间复杂度太大，于是转为用宽搜，把起始点放入队列中，队列中的节点是一个字符串，因为要找到最短路径，所以在取出队首节点时要知道该节点属于第几层被搜索的节点，即路径长度，我用了levels来保存当前遍历的是第几层的节点，然后扩展该节点，把编辑距离为1并且在字典中出现的字符串加入队尾，并从字典中删除该字符串。
     

     在找编辑距离为1的字符串时，我试了两种方法，一种是遍历字典，找到编辑记录为1的字符串，如果字典数目很大的话，每次都遍历字典耗时太多了，结果就是TLE，后来直接对节点字符串进行修改一个字符来得到扩展字符串才通过。

     class Solution {
     public:
         typedef queue
            
             > qq; int ladderLength(string start, string end, unordered_set
             
               &dict) { //Use queue to implement bfs operation qq q; q.push(start); dict.erase(start); int currLevelLens = 1, nextLevelLens; int levels = 1; //To be returned answer, the total bfs levels be traversed string front, str; while (!q.empty()) { nextLevelLens = 0; while (currLevelLens--) { // Traverse the node of current level string front = q.front(); q.pop(); if (front == end) return levels; for (int i=0; i
              
             
            

     
     
     

     但是这样的方法改变了dict的内容，有没有不改变dict的方法呢？我试了用一个unorder_set来保存被搜索过的字符串,但是耗时比前一种方法多。

     class Solution {
     public:
         typedef queue
           
            > qq;
         int ladderLength(string start, string end, unordered_set
            
              &dict) { //Use queue to implement bfs operation qq q; q.push(start); int currLevelLens = 1, nextLevelLens; int levels = 1; //To be returned answer, the total bfs levels be traversed string front, str; searchedStrs.insert(start); while (!q.empty()) { nextLevelLens = 0; while (currLevelLens--) { // Traverse the node of current level string front = q.front(); q.pop(); if (front == end) return levels; for (int i=0; i
             
               searchedStrs; }; 
             
            
           

     
     
     

     Python解法：

     有参考Google Norvig的拼写纠正例子：http://norvig.com/spell-correct.html

     class Solution:
         # @param word, a string
         # @return a list of transformed words
         def edit(self, word):
             alphabet = string.ascii_lowercase
             splits = [(word[:i],word[i:]) for i in range(len(word)+1)]
             replaces = [a+c+b[1:] for a,b in splits for c in alphabet if b]
             replaces.remove(word)
             return replaces
             
         # @param start, a string
         # @param end, a string
         # @param dict, a set of string
         # @return an integer
         def ladderLength(self, start, end, dict):
             currQueue = []
             currQueue.append(start)
             dict.remove(start)
             ret = 0
             while 1:
                 ret += 1
                 nextQueue = []
                 while len(currQueue):
                     s = currQueue.pop(0)
                     if s == end:
                         return ret
                     editWords = self.edit(s)
     
                     for word in editWords:
                         if word in dict:
                             dict.remove(word)
                             nextQueue.append(word)
                 if len(nextQueue)==0:
                     return 0
                 currQueue = nextQueue
             return 0