频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
单词接龙-LintCode
2017-07-19 11:42:44      个评论    来源:zhaohengchuan的博客  
收藏   我要投稿

给出两个单词(start和end)和一个字典,找到从start到end的最短转换序列

比如:

每次只能改变一个字母。

变换过程中的中间单词必须在字典中出现。

注意事项

如果没有转换序列则返回0。

所有单词具有相同的长度。

所有单词都只包含小写字母。

样例

给出数据如下:

start = “hit”

end = “cog”

dict = [“hot”,”dot”,”dog”,”lot”,”log”]

一个最短的变换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,

返回它的长度 5

#ifndef C120_H
#define C120_H
#include
#include
#include
#include
#include
#include
using namespace std;
class Solution {
public:
    /**
    * @param start, a string
    * @param end, a string
    * @param dict, a set of string
    * @return an integer
    */
    int ladderLength(string start, string end, unordered_set &dict) {
        // write your code here
        if (start == end)
            return 1;
        if (start.size() != end.size())
            return 0;
        if (start.empty() || end.empty() || dict.empty())
            return 0;
        queue path;
        path.push(start);
        map count;
        count[start] = 1;
        dict.erase(start);
        while (!path.empty())
        {
            string str = path.front();
            path.pop();
            int n = count[str];
            for (int i = 0; i < str.size(); ++i)
            {
                string temp = str;
                for (char j = 'a'; j <= 'z'; ++j)
                {
                    if (temp[i] == j)
                        continue;
                    else
                        temp[i] = j;
                    if (dict.find(temp) != dict.end())
                    {
                        path.push(temp);
                        count[temp] = n + 1;
                        dict.erase(temp);
                    }
                    if (temp == end)
                        return n + 1;
                }
            }

        }
        return 0;
    }
};
#endif
点击复制链接 与好友分享!回本站首页
上一篇:ajax+json+Struts2实现list传递
下一篇:数据结构(第二天)单向循环链表的创建,插入元素,(删除、查询元素跟单链表操作基本一致)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站