Word Ladder
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.
这道题数据规模dict.size() 最大4000+。
构建图(每两个可转换的单词连一条边)以后,bfs一边。
本身不难,不过非常容易超时。主要构建图是如果用N*N来搞的话,会超时。
加速1:
因此构建图可以采用别的方法:在找“hot”相邻的词时,可以改变hot中一个字符,例如“aot”,然后在dict里面找是否有。
这样的复杂度为O(N+N*logN*26*LEN), len为单词平均长度
只要26×len×LogN < N。那么就加速了。
加速2:
另外,其实构建图时,可以推迟构建全图。
每次要用到与某个词相邻的词时,再构建。这样会快点。
class Solution { public: bool cmp(const string& a, const string& b) { if (a.size() != b.size()) return false; bool flag = false; for (int i = 0; i < a.size(); ++i) { if (a[i] != b[i]){ if (flag == false) flag = true; else return false; } } return flag; } void getNext(const string& tmp, const unordered_set<string>& dict, vector<string> &v ) { for (int i = 0; i < tmp.size(); ++i) { for (int j = 0; j < 26; ++j) { if (tmp[i] == 'a' + j) continue; string t2 = tmp; t2[i] = 'a' + j; auto res = dict.find(t2); if (res != dict.end()){ v.push_back(t2); } } } } int ladderLength(string start, string end, unordered_set<string> &dict) { int dsize = dict.size(); queue<string> q; queue<int > l; unordered_set<string> visited; auto it = dict.find(start); if (it != dict.end()) { q.push(*it); visited.insert(*it); l.push(1); } else { for (auto i = dict.begin(); i != dict.end(); ++i) { if (cmp(start, *i)) { q.push(*i); visited.insert(*i); l.push(2); } } } int level; while (!q.empty()) { string cur = q.front(); q.pop(); level = l.front(); l.pop(); vector<string> v; getNext(cur, dict, v); for (int i = 0; i < v.size(); ++i) { if (v[i] == end) return level + 1; } for (int i = 0; i < v.size(); ++i) { if (visited.count(v[i]) == 0) { if (cmp(v[i], end)) return level + 2; else { q.push(v[i]); l.push(level + 1); visited.insert(v[i]); } } } } return 0; } };
class Solution { public: int ladderLength(string start, string end, unordered_set<string> &dict) { if (start == end) return 1; unordered_map<string, int> id; vector<string> str; int idx = 0; for (auto it = dict.begin(); it != dict.end(); ++it) { if (id.count(*it) > 0) continue; id[*it] = idx++; str.push_back(*it); } if (id.count(end) == 0) id[end] = idx++, str.push_back(end); int endid = id[end]; vector<bool> vis(idx, false); queue<int> q; int level = 2; vector<int> next; getnext(id, start, vis, next); if (vis[endid]) return level; while (!next.empty()) { vector<int> cur(next); next.clear(); for (int i = 0; i < cur.size(); i++) { getnext(id, str[cur[i]], vis, next); if (vis[endid]) return level+1; } level++; } return 0; } void getnext(const unordered_map<string,int> &id, string& a, vector<bool>& vis, vector<int> & res) { int len = a.size(); for (int i = 0; i < len; i++) { char c = a[i]; for (char t = 'a'; t < 'z'; t++) { if (t == c) continue; a[i] = t; auto it = id.find(a); if (it != id.end() && vis[it->second] == false) { vis[it->second] = true; res.push_back(it->second); } } a[i] = c; } } };
相关推荐
126.Word_Ladder_II_词语阶梯二【LeetCode单题讲解系列】
经典字梯游戏c++代码,经测试通过的哦,leetcode上面的题目
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
大佬的leetcode刷题笔记(c++版本)
vs code LeetCode 插件
leetcode中文版
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
自己做leecode题目的总结,做个分享从事服务端开发,少不了要接触网络编程。epoll作为linux下高性能网络服务器的必备技术至关重要,nginx、redis、skynet和大部分游戏服务器都使用到这一多路复用技术。...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
leetcode高频面试笔试题150+道,亲身总结。
LeetCode面试笔试题
LeetCode 刷题笔记
(C++)LeetCode刷题题解答案