Word Ladder

Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, 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.

解题思路：

第一的想法是用一个图来记录相邻关系，然后将问题转化成图的最短路径问题。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set& wordDict) {
        if(beginWord == endWord){
            return 1;
        }
        if(isNeibor(beginWord, endWord)){
            return 2;
        }
        if(wordDict.find(beginWord)==wordDict.end()){
            wordDict.insert(beginWord);
        }
        if(wordDict.find(endWord)==wordDict.end()){
            wordDict.insert(endWord);
        }
        //将set转化成vector
        vector wordVect;
        for(unordered_set::iterator it = wordDict.begin(); it!=wordDict.end(); it++){
            wordVect.push_back(*it);
        }
        int len = wordVect.size();
        vector> graph(len, vector());  //邻接表存储图
        int beginIndex = -1;
        int endIndex = -1;
        for(int i=0; i pre(len, -1);       //某个节点的前驱节点
        pre[beginIndex] = beginIndex;
        queue q({beginIndex});     //广度优先法
        bool flag = false;              //是否已经找到了路径
        while(!q.empty()){
            int c = q.front();
            q.pop();
            for(int i=0; i

 
转载请注明： » [LeetCode] Word Ladder

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->