http://oj.leetcode.com/problems/word-ladder/

图的最短路径问题，可以用最短路径算法，也可以深搜，也可以广搜。

深搜版本：

第一次写的时候，把sum和visited都自然的设置成了传引用，导致递归调用下去之后，再返回来，反而各种参数的值退不回来了。然后把sum和visited改成了传值，这样反而适应了本程序意图。可见，也不是什么时候都需要传引用的。具体在写程序的时候，需要传值还是传引用，要具体分析。传引用和传值的情况分别如下：

void DFS(string currentWord,string endWord,int &sum, unordered_set<string> &dict,map<string,bool>  &visited,int  &minDistance)
void DFS(string currentWord,string endWord,int &sum, unordered_set<string> &dict,map<string,bool>  &visited,int  &minDistance)
另外，还遇到了一个问题，在递归调用层次下去又上来后，对本层循环的，后续影响。所以又添加了两个变量，int tempSum;和map<string,bool> tempVisited;。给它们赋值成参数刚进来的样子，这样就摒除了同层循环间的相互影响。

深搜版本超时了，继续改……
#include <iostream>

#include <vector>

#include <string>

#include <unordered_set>

#include <map>

#include <hash_map>

#include <limits.h>

using namespace std;

class Solution {

public:

    int calcDistance(string a,string b)

    {

        int sum = ;

        for(int i = ;i<a.size();i++)

        {

            if(a[i]!=b[i])

                sum++;

        }

        return sum;

    }

    void DFS(string currentWord,string endWord,int  sum, unordered_set<string> &dict,map<string,bool>  visited,int  &minDistance)

    {

        if(calcDistance(currentWord,endWord)==)

        {

            sum++;

            if(minDistance>  sum)

                minDistance =  sum;

            return;

        }

        int tempSum;

        map<string,bool> tempVisited;

        for(unordered_set<string>::iterator iter = dict.begin();iter!=dict.end();iter++)

        {

            if(visited[*iter]==false && calcDistance(currentWord,*iter)==)

            {

                visited[*iter] = true;

                tempSum = sum;

                tempSum++;

                tempVisited = visited;

                DFS(*iter,endWord,tempSum,dict,visited,minDistance);

            }

        }

    }

    int ladderLength(string start, string end, unordered_set<string> &dict) {

        string currentWord = start;

        int sum = ;

        map<string,bool> visited;

        for(unordered_set<string>::iterator iter = dict.begin();iter!=dict.end();iter++)

            visited[*iter] = false;

        int minDistance = INT_MAX;

        DFS(currentWord,end,sum,dict,visited,minDistance);

        return  minDistance;

    }

};

    int main()

    {

        Solution *mySolution = new Solution();

        unordered_set<string> dict;

        dict.insert("hot");

        dict.insert("dot");

        dict.insert("dog");

        dict.insert("lot");

        dict.insert("log");

        string start = "hit";

        string end = "cog";

        cout<<mySolution->ladderLength(start,end,dict);

        return ;

    }

然后，写了一个广搜版本的，代码如下：

class Solution {

public:

    class node{

    public:

        int distance;

        string word;

        bool visited;

    public:

        node()

        {

            distance = ;

            word.clear();

            visited = false;

        }

    };

    int testDistance(string test,string end)

    {

        int distance = ;

        for(int i = ;i<test.size();i++)

            if(test[i]!= end[i])

                distance++;

        return distance;

    }

   int ladderLength(string start, string end, unordered_set<string> &dict) {

       vector<node*> wordVector;

       unordered_set<string>::iterator itor=dict.begin();

       for(int i = ;i<dict.size();i++)

       {

           node *myNode = new node();

           myNode->word = *itor;

           itor++;

           wordVector.push_back(myNode);

       }

       node *myNode = new node();

       myNode->word = start;

       queue<node*> wordQueue;

       wordQueue.push(myNode);

       node *topNode= new node();

       while(!wordQueue.empty())

       {

           topNode = wordQueue.front();

           wordQueue.pop();

           if(testDistance(topNode->word,end) == )

           {

               return topNode->distance+;

           }

           else

           {

               node *pIndexNode = new node();

               for(vector<node*>::iterator itor = wordVector.begin();itor!=wordVector.end();itor++)

               {

                   pIndexNode = *itor;

                   if(pIndexNode->visited == false && testDistance(pIndexNode->word,topNode->word)==)

                   {

                       pIndexNode->visited = true;

                       pIndexNode->distance = topNode->distance+;

                       wordQueue.push(pIndexNode);

                   }

               }

           }

       }

   }

};

在这个过程中，刚开始写的是

return topNode->distance++；就直接这样返回了，写程序过程中，细心不够，这样返回是distance本来的值，然后distance会++，但是那也没用了。

仍然没过。但是相比之下，广搜比深搜，在测试数据上有进步了。继续改进广搜版本，将testDistance函数改了，并且还是用了eraser函数，将已经加入过的元素删除了，代码如下：

#include <iostream>

#include <vector>

#include <string>

#include <unordered_set>

#include <queue>

using namespace std;

class Solution {

public:

    class node{

    public:

        int distance;

        string word;

    public:

        node()

        {

            distance = ;

            word.clear();

        }

    };

    bool testDistance(string test,string end)

    {

        int distance = ;

        for(int i = ;i<test.size();i++)

        {

            if(test[i]!= end[i])

                distance++;

            if(distance>=)

                return false;

        }

        return true;

    }

   int ladderLength(string start, string end, unordered_set<string> &dict) {

       vector<node*> wordVector;

       unordered_set<string>::iterator itor=dict.begin();

       for(int i = ;i<dict.size();i++)

       {

           node *myNode = new node();

           myNode->word = *itor;

           itor++;

           wordVector.push_back(myNode);

       }

       node *myNode = new node();

       myNode->word = start;

       queue<node*> wordQueue;

       wordQueue.push(myNode);

       node *topNode= new node();

       while(!wordQueue.empty())

       {

           topNode = wordQueue.front();

           wordQueue.pop();

           if(testDistance(topNode->word,end))

           {

               return topNode->distance+;

           }

           else

           {

               node *pIndexNode = new node();

               for(vector<node*>::iterator itor = wordVector.begin();itor!=wordVector.end();)

               {

                   pIndexNode = *itor;

                   if(testDistance(pIndexNode->word,topNode->word))

                   {

                       pIndexNode->distance = topNode->distance+;

                       wordQueue.push(pIndexNode);

                       itor = wordVector.erase(itor);

                   }

                   else

                       itor++;

               }

           }

       }

   }

};

    int main()

    {

        Solution *mySolution = new Solution();

        unordered_set<string> dict;

        dict.insert("hot");

        dict.insert("dot");

        dict.insert("dog");

        dict.insert("lot");

        dict.insert("log");

        string start = "hit";

        string end = "cog";

        cout<<mySolution->ladderLength(start,end,dict);

        return ;

    }

虽然每一步都有学习到新东西，也学会了些深搜和广搜，但是这道题目仍然超时，现在考虑用空间换时间。

#include <iostream>

#include <vector>

#include <string>

#include <unordered_set>

#include <unordered_map>

#include <queue>

using namespace std;

class Solution {

public:

    bool testDistance(string test,string end)

    {

        int distance = ;

        for(int i = ;i<test.size();i++)

        {

            if(test[i]!= end[i])

                distance++;

            if(distance>=)

                return false;

        }

        return true;

    }

    void BuildAdjacentList(string &word, unordered_map< string,unordered_set<string> >&adjacentList,const unordered_set<string> &dict)

    {

        string original = word;

        for(size_t pos = ;pos<word.size();pos++)

        {

            char beforeChange = ' ';

            for(int i = 'a';i<'z';++i)

            {

                beforeChange = word[pos];

                if(beforeChange == i)

                {

                    continue;

                }

                word[pos] = i;

                if(dict.count(word)>)

                {

                    auto iter = adjacentList.find(original);

                    if(iter!= adjacentList.end())

                        iter->second.insert(word);

                    else

                    {

                        adjacentList.insert(pair<string,unordered_set<string> >(original,unordered_set<string>()));

                        adjacentList[original].insert(word);

                    }

                }

                word[pos] = beforeChange;

            }

        }

    }

   int ladderLength(string start, string end, unordered_set<string> &dict) {

       queue<pair<string,int> > wordQueue;

       wordQueue.push(make_pair(start,));

       unordered_map< string,unordered_set<string> > adjacentList;

       string topWord;

       int ans = ;

       unordered_set<string> visited;

       visited.insert(start);

       while(!wordQueue.empty())

       {

           topWord = wordQueue.front().first;

           if(testDistance(topWord,end))

           {

               return wordQueue.front().second+;

           }

           else

           {

               BuildAdjacentList(topWord,adjacentList,dict);

               auto iter = adjacentList.find(topWord);

               if(iter!= adjacentList.end())

               {

                   for(unordered_set<string>::iterator iterset = iter->second.begin();iterset!= iter->second.end();iterset++)

                   {

                       if(visited.find(*iterset)==visited.end())

                       {

                           wordQueue.push(make_pair(*iterset,wordQueue.front().second+));

                           visited.insert(*iterset);

                       }

                   }

               }

           }

           wordQueue.pop();

       }

       return ;

   }

};

    int main()

    {

        Solution *mySolution = new Solution();

        unordered_set<string> dict;

        dict.insert("hot");

        //dict.insert("dot");

        dict.insert("dog");

        //dict.insert("lot");

        //dict.insert("log");

        string start = "hot";

        string end = "dog";

        cout<<mySolution->ladderLength(start,end,dict);

        return ;

    }

上面的这份代码，终于AC了，果然考察的重点在另一个思路上。其实，也用不着用空间来存储。比如可以使用更精简的代码，如下：

class Solution{

public:

    int ladderLength(string start,string end,unordered_set<string> &dict)

    {

        queue<pair<string ,int > > wordQueue;

        unordered_set<string> visited;

        wordQueue.push(make_pair(start,));

        visited.insert(start);

        while(!wordQueue.empty())

        {

            string curStr = wordQueue.front().first;

            int curStep = wordQueue.front().second;

            wordQueue.pop();

            for(int i = ;i<curStr.size();i++)

            {

                string tmp = curStr;

                for(int j = ;j<;++j)

                {

                    tmp[i] = j+'a';

                    if(tmp == end)

                        return curStep+;

                    if(visited.find(tmp) == visited.end() && dict.find(tmp)!=dict.end())

                    {

                        wordQueue.push(make_pair(tmp,curStep+));

                        visited.insert(tmp);

                    }

                }

            }

        }

        return ;

    }

};

加油！

 其实，这道题的重点不在于深搜、广搜剪枝之类的。换个角度说的话，dict很大，多次遍历它的话，影响时间，然后换个思路……

最新文章

  1. while do while以及穷举和迭代
  2. java：String使用equals和==比较的区别
  3. bash里，echo对换行符的处理
  4. 【Qt】测测你对Qt的了解–Qt工具知多少
  5. web离线应用
  6. 原生JS与jQuery操作DOM对比
  7. 0412ooday01.txt=============对象和类（上）
  8. Ubuntu系统多屏幕时 触摸屏如何分屏定位
  9. php关于Session和cookie总结
  10. SaltStack 模块
  11. react router @4 和 vue路由 详解(七)react路由守卫
  12. rpm使用
  13. PR回写 所有物料规划PR时对净需求+最小采购批量+安全库存+舍入值的先后考虑逻辑
  14. 永久激活win和office
  15. python web调用docker-py
  16. 关于LaaS,PaaS,SaaS一些个人的理解
  17. spring底层原理解析
  18. MySQL 8.0复制性能的提升（翻译）
  19. OpenCV(C++版)图像读取，创建，复制，保存，显示
  20. XML简单学习

热门文章

  1. Linux Ptrace 详解
  2. 配置基于Vim的Python开发环境
  3. Redis的安装、服务配置
  4. pyqt设计
  5. 安装openstack同步数据库时出错解决方法
  6. jmeter中重要组件及其执行顺序
  7. BZOJ 3326: [Scoi2013]数数
  8. 光学字符识别OCR-2
  9. c#利用反射实现对类中的常量进行取值和对应常量的注释
  10. 教你玩App怎么赚钱（一）