题目
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
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.
分析
广搜
代码
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
return BFS(start,end,dict);
}
private:
int BFS(string start,string end,unordered_set<string> &dict){
queue<pair<string,int> > q;
q.push(make_pair(start,1));
unordered_set<string> visited;
visited.insert(start);
bool found = false;
while(!q.empty()){
pair<string,int> cur = q.front();
q.pop();
string word = cur.first;
int len = word.size();
for(int i = 0;i < len;++i){
string newWord(word);
for(int j = 0;j < 26;++j){
newWord[i] = 'a' + j;
if(newWord == end){
found = true;
return cur.second+1;
}
if(dict.count(newWord) > 0 && visited.count(newWord) == 0){
visited.insert(newWord);
q.push(make_pair(newWord,cur.second+1));
}
}
}
}
if(!found){
return 0;
}
}
};
int main(){
Solution s;
unordered_set<string> set = {"hot","dot","dog","lot","log"};
string start("hit");
string end("cog");
int result = s.ladderLength(start,end,set);
cout<<result<<endl;
return 0;
}
运行时间
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
数据来源:中国劳动统计NJ-2023版
数据来源:中国人口与就业统计NJ-2023版
Smart继电器编程器操作手册
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
数据来源:中国人口与就业统计NJ-2023版
数据来源:中国人口与就业统计NJ-2023版
基于matlab实现的图像几何校正的程序,根据靶图将tiger图像从鱼眼形变恢复.rar
毕业论文(设计)—旅游资源管理系统设计与实现论文.doc
数据来源:中国劳动统计NJ-2023版
数据来源:中国电力统计NJ-2021版
引入dynamic-datasource-spring-boot-starter。 spring-boot 1.5.x 2.x.x <dependency> <groupId>com.baomidou</groupId> <artifactId>dynamic-datasource-spring-boot-starter</artifactId> <version>${version}</version> </dependency> spring-boot3及以上 <dependency> <groupId>com.baomidou</groupId> <artifactId>dynamic-datasource-spring-boot3-starter</artifactId> <version>${version}</version> </dependency> 配置数据源。 spring: datasource: dynamic: enabled: true #启用动态数据源,默认true
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
基于HarmonyOS 4开发的一款新闻类的鸿蒙APP源代码
基于matlab实现遗传算法无功优化,基于掌纹识别的在线身份验证 识别算法本科毕设,是本科毕设的题目。.rar
【毕业设计】基于C和Access的图书管理系统设计与实现.doc
附件是 华为 OD 机考攻略_加强版,文件绿色安全,请大家放心下载,仅供交流学习使用,无任何商业目的!
数据来源:中国人口与就业统计NJ-2023版
基于RFID的资产管理系统设计与实现.doc
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
数据来源:中国人口与就业统计NJ-2023版