leetcode-WordLadder

简介:

Word Ladder

   Total Accepted: 10243  Total Submissions: 58160 My Submissions

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.

Have you been asked this question in an interview?

 


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

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

<span style="font-size:14px;">class Solution {
public:
    typedef queue<string,deque<string>> qq;
    int ladderLength(string start, string end, unordered_set<string> &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<front.size(); ++i) {
                    for (char j='a'; j<='z'; ++j) { // transform
                        if (front[i]=='j')
                            continue;
                        str = front;
                        str[i] = j;    
                        if (dict.find(str) != dict.end()) { 
                            ++nextLevelLens;
                            q.push(str);
                            dict.erase(str);
                        }
                    }
                }
            }
            currLevelLens = nextLevelLens;
            ++levels;
        }
        return 0;
    }
    
};
</span>


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

class Solution {
public:
    typedef queue<string,deque<string>> qq;
    int ladderLength(string start, string end, unordered_set<string> &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<front.size(); ++i) {
                    for (char j='a'; j<='z'; ++j) { // transform
                        if (front[i]==j)
                            continue;
                        str = front;
                        str[i] = j;
                        
                        if (searchedStrs.find(str) == searchedStrs.end() && dict.find(str) != dict.end()) { 
                            ++nextLevelLens;
                            q.push(str);
                            //dict.erase(str);
                            searchedStrs.insert(str);
                        }
                    }
                }
            }
            currLevelLens = nextLevelLens;
            ++levels;
        }
        return 0;
    }
private:
    unordered_set<string> 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
 




本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5315396.html,如需转载请自行联系原作者
相关文章
|
5天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
16天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1315 5
|
2天前
|
监控 JavaScript Java
基于大模型技术的反欺诈知识问答系统
随着互联网与金融科技发展,网络欺诈频发,构建高效反欺诈平台成为迫切需求。本文基于Java、Vue.js、Spring Boot与MySQL技术,设计实现集欺诈识别、宣传教育、用户互动于一体的反欺诈系统,提升公众防范意识,助力企业合规与用户权益保护。
|
15天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1365 87
|
2天前
|
JavaScript Java 大数据
基于JavaWeb的销售管理系统设计系统
本系统基于Java、MySQL、Spring Boot与Vue.js技术,构建高效、可扩展的销售管理平台,实现客户、订单、数据可视化等全流程自动化管理,提升企业运营效率与决策能力。
|
4天前
|
弹性计算 安全 数据安全/隐私保护
2025年阿里云域名备案流程(新手图文详细流程)
本文图文详解阿里云账号注册、服务器租赁、域名购买及备案全流程,涵盖企业实名认证、信息模板创建、域名备案提交与管局审核等关键步骤,助您快速完成网站上线前的准备工作。
197 82
2025年阿里云域名备案流程(新手图文详细流程)