x*o
2 楼
客观地分析一下。
岳灵珊:会武功、会做饭、会女工、名声好、名望高。
任盈盈:会吹箫。
只要是男人,就该选任盈盈!
岳灵珊:会武功、会做饭、会女工、名声好、名望高。
任盈盈:会吹箫。
只要是男人,就该选任盈盈!
w*x
3 楼
这题怎么那么别扭,原来目标单词不在字典里...
还有我咋超时了...
还有我咋超时了...
i*e
5 楼
贴贴你代码?
w*x
7 楼
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
unordered_set visited;
visited.insert(start);
queue que;
que.push(start);
int nCurLev = 1;
int nCurNum = 1;
int nNextNum = 0;
while (!que.empty())
{
string strCur = que.front();
que.pop();
nCurNum--;
for (unordered_set::iterator it = dict.begin();
it != dict.end(); it++)
{
if (visited.find(*it) == visited.end() && canChng(*it,
strCur))
{
que.push(*it);
visited.insert(*it);
nNextNum++;
}
}
if (canChng(end, strCur))
return nCurLev+1;
if (nCurNum <= 0)
{
nCurLev++;
nCurNum = nNextNum;
nNextNum = 0;
}
}
return 0;
}
bool canChng(string a, string b)
{
if (a.length() != b.length())
return false;
bool bDiff = false;
for (int i = 0; i < a.length(); i++)
{
if (a.at(i) != b.at(i))
{
if (bDiff)
return false;
bDiff = true;
}
}
return bDiff;
}
};
public:
int ladderLength(string start, string end, unordered_set
unordered_set
visited.insert(start);
queue
que.push(start);
int nCurLev = 1;
int nCurNum = 1;
int nNextNum = 0;
while (!que.empty())
{
string strCur = que.front();
que.pop();
nCurNum--;
for (unordered_set
it != dict.end(); it++)
{
if (visited.find(*it) == visited.end() && canChng(*it,
strCur))
{
que.push(*it);
visited.insert(*it);
nNextNum++;
}
}
if (canChng(end, strCur))
return nCurLev+1;
if (nCurNum <= 0)
{
nCurLev++;
nCurNum = nNextNum;
nNextNum = 0;
}
}
return 0;
}
bool canChng(string a, string b)
{
if (a.length() != b.length())
return false;
bool bDiff = false;
for (int i = 0; i < a.length(); i++)
{
if (a.at(i) != b.at(i))
{
if (bDiff)
return false;
bDiff = true;
}
}
return bDiff;
}
};
i*e
9 楼
如果字典很大怎么办?
m*f
10 楼
岳灵珊性取向可议,任盈盈就不同,主动远离东方不败。
p*p
11 楼
large TLE了
不过ladder 1判断比较奇葩:hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
list queue;
set visited;
map stepMap;
queue.push_back(start);
visited.insert(start);
stepMap[start] = 1;
while (!queue.empty()) {
string s = queue.front();
queue.pop_front();
if (diffByOne(s, end)) return stepMap[s] + 1;
int currentStep = stepMap[s];
for (string strInDict : dict) {
if (visited.find(strInDict) != visited.end()) continue;
if (diffByOne(s, strInDict)) {
queue.push_back(strInDict);
visited.insert(strInDict);
stepMap[strInDict] = currentStep + 1;
}
}
}
return 0;
}
bool diffByOne(string &s1, string &s2) {
if (s1.size() != s2.size()) return false;
int diff = 0;
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) ++diff;
if (diff > 1) return false;
}
return diff == 1 ? true : false;
}
};
不过ladder 1判断比较奇葩:hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
class Solution {
public:
int ladderLength(string start, string end, unordered_set
// Start typing your C/C++ solution below
// DO NOT write int main() function
list
set
map
queue.push_back(start);
visited.insert(start);
stepMap[start] = 1;
while (!queue.empty()) {
string s = queue.front();
queue.pop_front();
if (diffByOne(s, end)) return stepMap[s] + 1;
int currentStep = stepMap[s];
for (string strInDict : dict) {
if (visited.find(strInDict) != visited.end()) continue;
if (diffByOne(s, strInDict)) {
queue.push_back(strInDict);
visited.insert(strInDict);
stepMap[strInDict] = currentStep + 1;
}
}
}
return 0;
}
bool diffByOne(string &s1, string &s2) {
if (s1.size() != s2.size()) return false;
int diff = 0;
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) ++diff;
if (diff > 1) return false;
}
return diff == 1 ? true : false;
}
};
i*e
13 楼
关于怎么测下一步是不是合法:
每一个字母'a'-'z'遍历,再看是否在字典里的复杂度 = 26 * n (n = 字的长度)
unordered_set 的查询是 O(1) 的。
遍历所有字典里的字然后一个一个比较是 n * dictionary_size,复杂度自然就上去
了。
每一个字母'a'-'z'遍历,再看是否在字典里的复杂度 = 26 * n (n = 字的长度)
unordered_set 的查询是 O(1) 的。
遍历所有字典里的字然后一个一个比较是 n * dictionary_size,复杂度自然就上去
了。
q*l
14 楼
令狐冲比较憨,得配个智商情商都高的。
a*o
15 楼
我来贴个能过的,比较丑,大家见谅...
int ladderLength(string start, string end, tr1::unordered_set &dict)
{
set contain;
int count = 1;
queue list[2];
list[0].push(start);
while (list[0].size()!= 0 || list[1].size()!=0){
int oldlist = 0;
int newlist = 1;
if (list[0].size()== 0){
oldlist = 1;
newlist = 0;
}
while (list[oldlist].size() != 0){
string curr = list[oldlist].front();
list[oldlist].pop();
if (contain.count(curr) > 0) continue;
contain.insert(curr);
for (int i = 0; i< curr.size(); i++){
for (int j = 0; j<26; j++){
char temp = curr[i];
char newtemp = (char) ('a'+j);
if (temp != newtemp){
string newcurr = curr;
newcurr[i] = newtemp;
if (newcurr == end) return count
+1;
if (dict.count(newcurr)> 0){
list[newlist].push(
newcurr);
}
}
}
}
}
count ++;
}
return 0;
}
【在 p****e 的大作中提到】
: rt
int ladderLength(string start, string end, tr1::unordered_set
{
set
int count = 1;
queue
list[0].push(start);
while (list[0].size()!= 0 || list[1].size()!=0){
int oldlist = 0;
int newlist = 1;
if (list[0].size()== 0){
oldlist = 1;
newlist = 0;
}
while (list[oldlist].size() != 0){
string curr = list[oldlist].front();
list[oldlist].pop();
if (contain.count(curr) > 0) continue;
contain.insert(curr);
for (int i = 0; i< curr.size(); i++){
for (int j = 0; j<26; j++){
char temp = curr[i];
char newtemp = (char) ('a'+j);
if (temp != newtemp){
string newcurr = curr;
newcurr[i] = newtemp;
if (newcurr == end) return count
+1;
if (dict.count(newcurr)> 0){
list[newlist].push(
newcurr);
}
}
}
}
}
count ++;
}
return 0;
}
【在 p****e 的大作中提到】
: rt
f*c
16 楼
岳灵珊太各色
w*x
17 楼
) {
这个也超时了
【在 p*****p 的大作中提到】
: large TLE了
: 不过ladder 1判断比较奇葩:hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
: class Solution {
: public:
: int ladderLength(string start, string end, unordered_set
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: list
: set
: map
i*e
19 楼
是比较奇怪,但仔细看好规则:
Each intermediate word must exist in the dictionary
start 和 end 都不是 intermediate word,所以字典可有可无。
) {
【在 p*****p 的大作中提到】
: large TLE了
: 不过ladder 1判断比较奇葩:hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
: class Solution {
: public:
: int ladderLength(string start, string end, unordered_set &dict) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: list queue;
: set visited;
: map stepMap;
Each intermediate word must exist in the dictionary
start 和 end 都不是 intermediate word,所以字典可有可无。
) {
【在 p*****p 的大作中提到】
: large TLE了
: 不过ladder 1判断比较奇葩:hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
: class Solution {
: public:
: int ladderLength(string start, string end, unordered_set
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: list
: set
: map
i*e
33 楼
你要的是 unordered_multimap 吧。
一个 key 可以 map 到好几个 value.
一个 key 可以 map 到好几个 value.
f*t
35 楼
public int ladderLength(String start, String end, HashSet dict) {
if (start == null || end == null || start.length() != end.length())
return 0;
int dist = 1;
HashSet used = new HashSet();
HashSet cur = new HashSet();
cur.add(start);
while(!cur.isEmpty()) {
HashSet newCur = new HashSet();
dist++;
for (String s : cur) {
char[] str = s.toCharArray();
for (int i = 0; i < str.length; i++) {
for (int j = 0; j < 26; j++) {
if (str[i] != (char)('a' + j)) {
char temp = str[i];
str[i] = (char)('a' + j);
String candidate = new String(str);
if (candidate.equals(end))
return dist;
if (!used.contains(candidate) && dict.contains(
candidate)) {
newCur.add(candidate);
used.add(candidate);
}
str[i] = temp;
}
}
}
}
cur = newCur;
}
return 0;
}
if (start == null || end == null || start.length() != end.length())
return 0;
int dist = 1;
HashSet
HashSet
cur.add(start);
while(!cur.isEmpty()) {
HashSet
dist++;
for (String s : cur) {
char[] str = s.toCharArray();
for (int i = 0; i < str.length; i++) {
for (int j = 0; j < 26; j++) {
if (str[i] != (char)('a' + j)) {
char temp = str[i];
str[i] = (char)('a' + j);
String candidate = new String(str);
if (candidate.equals(end))
return dist;
if (!used.contains(candidate) && dict.contains(
candidate)) {
newCur.add(candidate);
used.add(candidate);
}
str[i] = temp;
}
}
}
}
cur = newCur;
}
return 0;
}
b*u
36 楼
从两头往中间BFS,还能快点
x*6
37 楼
牛啊,等着leetcode刷新题。。。
g*9
39 楼
写了一个能过大数据test的C++版本,回馈版友了
大家见笑了。。
单纯的建立图,再暴力BFS确实过不了大数据的,平方复杂度在大数据时立刻超时
class Solution {
public:
int dis(const string& a, const string& b) {
int n = a.size();
if (n != b.size()) {
return -1;
}
int diff = 0;
int i;
for (i = 0; i < a.size(); i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 1) {
return -1;
}
}
} // for
return diff;
}
void gen(const string& s, vector & v) {
v.clear();
int n = s.size();
string scopy;
char c;
int i;
for (i = 0; i < n; i++) {
scopy = s;
for (c = 'a'; c <= 'z'; c++) {
if (s[i] != c) {
scopy[i] = c;
v.push_back(scopy);
}
}
}
return;
}
int ladderLength(string start, string end, unordered_set &dict) {
int n = start.size();
if (n != end.size()) {
return 0;
}
unordered_set::iterator it;
unordered_map visited;
unordered_map::iterator mt;
for (it = dict.begin(); it != dict.end(); it++) {
visited[*it] = 0;
}
visited[start] = 1;
deque q;
q.push_back(start);
string k, c;
vector can;
int i;
while (1) {
if (q.empty()) {
return 0;
}
k = q.front();
q.pop_front();
gen(k, can);
for (i = 0; i < can.size(); i++) {
string & w = can[i];
mt = visited.find(w);
if (mt != visited.end() &&
(mt->second == 0 || w == end)) {
q.push_back(w);
mt->second = visited[k] + 1;
if (w == end) {
return mt->second;
}
}
}
} // while
return 0;
}
};
大家见笑了。。
单纯的建立图,再暴力BFS确实过不了大数据的,平方复杂度在大数据时立刻超时
class Solution {
public:
int dis(const string& a, const string& b) {
int n = a.size();
if (n != b.size()) {
return -1;
}
int diff = 0;
int i;
for (i = 0; i < a.size(); i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 1) {
return -1;
}
}
} // for
return diff;
}
void gen(const string& s, vector
v.clear();
int n = s.size();
string scopy;
char c;
int i;
for (i = 0; i < n; i++) {
scopy = s;
for (c = 'a'; c <= 'z'; c++) {
if (s[i] != c) {
scopy[i] = c;
v.push_back(scopy);
}
}
}
return;
}
int ladderLength(string start, string end, unordered_set
int n = start.size();
if (n != end.size()) {
return 0;
}
unordered_set
unordered_map
unordered_map
for (it = dict.begin(); it != dict.end(); it++) {
visited[*it] = 0;
}
visited[start] = 1;
deque
q.push_back(start);
string k, c;
vector
int i;
while (1) {
if (q.empty()) {
return 0;
}
k = q.front();
q.pop_front();
gen(k, can);
for (i = 0; i < can.size(); i++) {
string & w = can[i];
mt = visited.find(w);
if (mt != visited.end() &&
(mt->second == 0 || w == end)) {
q.push_back(w);
mt->second = visited[k] + 1;
if (w == end) {
return mt->second;
}
}
}
} // while
return 0;
}
};
d*g
40 楼
第二题要过大集合还真不容易。。。
c*a
41 楼
写了个java的第一题
large的时间真长
Run Status: Accepted!
Program Runtime: 1460 milli secs
import java.util.Set;
import java.util.HashSet;
import java.util.Hashtable;
public class Solution {
public int ladderLength(String start, String end, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
Queue queue = new LinkedList();
Set visited = new HashSet();
Hashtable path = new Hashtable();
List res = new ArrayList();
queue.add(start);
visited.add(start);
while(queue.size()>0){
String prev = queue.poll();
for(String curr: generate(prev, dict)){
if(curr.equals(end)){
res.add(end);
while(prev!=null){
res.add(0,prev);
prev = path.get(prev);
}
return res.size();
}
if(!visited.contains(curr)){
visited.add(curr);
queue.add(curr);
path.put(curr, prev);
}
}
}
return 0;
}
public Set generate(String s, HashSet dict){
Set words = new HashSet();
for(int i =0;i for(char j = 'a'; j<='z';j++){
char[] chs = s.toCharArray();
if(chs[i]!=j ){
chs[i] = j;
String ns = new String(chs);
if(dict.contains(ns))
words.add(ns);
}
}
}
return words;
}
}
large的时间真长
Run Status: Accepted!
Program Runtime: 1460 milli secs
import java.util.Set;
import java.util.HashSet;
import java.util.Hashtable;
public class Solution {
public int ladderLength(String start, String end, HashSet
// Start typing your Java solution below
// DO NOT write main() function
Queue
Set
Hashtable
List
queue.add(start);
visited.add(start);
while(queue.size()>0){
String prev = queue.poll();
for(String curr: generate(prev, dict)){
if(curr.equals(end)){
res.add(end);
while(prev!=null){
res.add(0,prev);
prev = path.get(prev);
}
return res.size();
}
if(!visited.contains(curr)){
visited.add(curr);
queue.add(curr);
path.put(curr, prev);
}
}
}
return 0;
}
public Set
Set
for(int i =0;i
char[] chs = s.toCharArray();
if(chs[i]!=j ){
chs[i] = j;
String ns = new String(chs);
if(dict.contains(ns))
words.add(ns);
}
}
}
return words;
}
}
i*e
42 楼
word ladder II 有人过了 large tests 吗?
我抛砖引玉一下吧,希望有大牛可以提出更好的解法。
思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下,果然简洁很多,
整个程序不到50行。
基于程序可读性,所以 bottom up 返回路径,产生了很多不必要的拷贝而导致效率会
差很多。但路径组合没那么多,所以性能上也没什么影响。
typedef unordered_multimap Map;
typedef pair PairIter;
vector> findLadders(string start, string end, unordered_set<
string> &dict) {
Map map, map2;
queue q, q2;
q.push(start);
bool goal = false;
while (!q.empty()) {
string word = q.front();
q.pop();
for (int i = 0; i < start.length(); i++) {
string s = word;
for (char c = 'a'; c <= 'z'; c++) {
s[i] = c;
if (s == word) continue;
if (s == end) goal = true;
if (map.find(s) == map.end() && dict.find(s) != dict.end()) {
if (map2.find(s) == map2.end()) {
q2.push(s);
}
map2.insert(make_pair(s, word));
}
}
}
if (q.empty()) {
swap(q, q2);
map.insert(map2.begin(), map2.end());
map2.clear();
if (goal) return print(map, end, start);
}
}
return vector>();
}
// backtrack to reconstruct the path from start -> end.
vector> print(Map &map, string s, string start, int depth = 0
) {
if (depth > 0 && s == start) {
return vector>(1, vector(1, s));
}
vector> ret;
for (PairIter it = map.equal_range(s); it.first != it.second; ++it.first
) {
vector> temp = print(map, it.first->second, start,
depth+1);
for (int i = 0; i < temp.size(); i++) {
temp[i].push_back(s);
}
ret.insert(ret.end(), temp.begin(), temp.end());
}
return ret;
}
我抛砖引玉一下吧,希望有大牛可以提出更好的解法。
思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下,果然简洁很多,
整个程序不到50行。
基于程序可读性,所以 bottom up 返回路径,产生了很多不必要的拷贝而导致效率会
差很多。但路径组合没那么多,所以性能上也没什么影响。
typedef unordered_multimap
typedef pair
vector
string> &dict) {
Map map, map2;
queue
q.push(start);
bool goal = false;
while (!q.empty()) {
string word = q.front();
q.pop();
for (int i = 0; i < start.length(); i++) {
string s = word;
for (char c = 'a'; c <= 'z'; c++) {
s[i] = c;
if (s == word) continue;
if (s == end) goal = true;
if (map.find(s) == map.end() && dict.find(s) != dict.end()) {
if (map2.find(s) == map2.end()) {
q2.push(s);
}
map2.insert(make_pair(s, word));
}
}
}
if (q.empty()) {
swap(q, q2);
map.insert(map2.begin(), map2.end());
map2.clear();
if (goal) return print(map, end, start);
}
}
return vector
}
// backtrack to reconstruct the path from start -> end.
vector
) {
if (depth > 0 && s == start) {
return vector
}
vector
for (PairIter it = map.equal_range(s); it.first != it.second; ++it.first
) {
vector
depth+1);
for (int i = 0; i < temp.size(); i++) {
temp[i].push_back(s);
}
ret.insert(ret.end(), temp.begin(), temp.end());
}
return ret;
}
d*e
43 楼
贴个第一题,
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
queue q;
queue cnt;
unordered_set visited;
q.push(start);
cnt.push(1);
if (start != end) visited.insert(start);
while (!q.empty()) {
string word = q.front(); q.pop();
int dist = cnt.front(); cnt.pop();
if (dist > 1 && word == end) return dist;
for (int i = 0; i < word.size(); i++) {
string copy(word);
for (char c = 'a'; c <= 'z'; c++)
if (c != word[i]) {
copy[i] = c;
if (dict.find(copy) != dict.end() &&
visited.find(copy) == visited.end()) {
q.push(copy);
cnt.push(dist+1);
visited.insert(copy);
}
}
}
}
return 0;
}
};
【在 p****e 的大作中提到】
: rt
class Solution {
public:
int ladderLength(string start, string end, unordered_set
queue
queue
unordered_set
q.push(start);
cnt.push(1);
if (start != end) visited.insert(start);
while (!q.empty()) {
string word = q.front(); q.pop();
int dist = cnt.front(); cnt.pop();
if (dist > 1 && word == end) return dist;
for (int i = 0; i < word.size(); i++) {
string copy(word);
for (char c = 'a'; c <= 'z'; c++)
if (c != word[i]) {
copy[i] = c;
if (dict.find(copy) != dict.end() &&
visited.find(copy) == visited.end()) {
q.push(copy);
cnt.push(dist+1);
visited.insert(copy);
}
}
}
}
return 0;
}
};
【在 p****e 的大作中提到】
: rt
w*t
44 楼
career 150上有这个题,解法就是 BFS + hashmap存路径,算是标准的解法把。
j*g
45 楼
第二个过了Large的 轻拍
class Solution {
public:
vector> findLadders(string start, string end, unordered_
set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=dict.size();
int res=1;
int done=0;
stack stk[2];
unordered_set used;
unordered_map > path;
unordered_set level;
int index=0;
stk[index%2].push(start);
used.insert(start);
vector> rtn;
while(!stk[index%2].empty()&&done!=2){
if(res == size+2)
return rtn;
string current=stk[index%2].top();
stk[index%2].pop();
int N=current.length();
for(int i=0;i for(char s='a';s<='z';s++){
if(current[i]!=s){
string tmp = current;
tmp[i]=s;
if(dict.find(tmp)!=dict.end()||!tmp.compare(end)){
if(path.find(tmp)==path.end()){
path[tmp]=vector (1,current);
level.insert(tmp);
}else{
if(level.find(tmp)!=level.end())
path[tmp].push_back(current);
}
if(!tmp.compare(end))
done=1;
else if(used.find(tmp)==used.end()){
stk[(index+1)%2].push(tmp);
used.insert(tmp);
}
}
}
}
}
if(stk[index%2].empty()){
index=index+1;
res++;
level.clear();
if(done)
done=2;
}
}
if(done)
getpath(start, end, path, rtn, vector(0,"a"));
return rtn;
}
void getpath(string start, string end, unordered_map string> > &path, vector > &rtn, vector route){
if(!start.compare(end)&&route.size()!=0){
route.push_back(end);
reverse(route.begin(), route.end());
rtn.push_back(route);
return;
}
vector up = path[end];
route.push_back(end);
for(int i=0; i getpath(start, up[i], path, rtn, route);
}
}
};
class Solution {
public:
vector
set
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=dict.size();
int res=1;
int done=0;
stack
unordered_set
unordered_map
unordered_set
int index=0;
stk[index%2].push(start);
used.insert(start);
vector
while(!stk[index%2].empty()&&done!=2){
if(res == size+2)
return rtn;
string current=stk[index%2].top();
stk[index%2].pop();
int N=current.length();
for(int i=0;i
if(current[i]!=s){
string tmp = current;
tmp[i]=s;
if(dict.find(tmp)!=dict.end()||!tmp.compare(end)){
if(path.find(tmp)==path.end()){
path[tmp]=vector
level.insert(tmp);
}else{
if(level.find(tmp)!=level.end())
path[tmp].push_back(current);
}
if(!tmp.compare(end))
done=1;
else if(used.find(tmp)==used.end()){
stk[(index+1)%2].push(tmp);
used.insert(tmp);
}
}
}
}
}
if(stk[index%2].empty()){
index=index+1;
res++;
level.clear();
if(done)
done=2;
}
}
if(done)
getpath(start, end, path, rtn, vector
return rtn;
}
void getpath(string start, string end, unordered_map
if(!start.compare(end)&&route.size()!=0){
route.push_back(end);
reverse(route.begin(), route.end());
rtn.push_back(route);
return;
}
vector
route.push_back(end);
for(int i=0; i
}
}
};
c*t
46 楼
大侠。
我刚开始做第一题,用的是一贯的DFS+recursion, 是你说的26*length的作法,结果大
数据超时了。这类型的题(比如word search),我都习惯用DFS+recursion,请问用
recursion解这类题是不是坏习惯?还有说BFS比DFS快,是general指所有这类型的题,
还是因为这道题求的是shortest transform, 所以能提前退出?
多谢!
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来,就要遍历hashtable 里所有的字。
: 这很不efficient,因为字典内可能含有很多字。还有就是,hashtable 遍历好像很不
: efficient,只有查询最适合。
: 倒过来思考:
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6,那么所有可能性就是 26*6 = 156,远远小于字典内的个数。
我刚开始做第一题,用的是一贯的DFS+recursion, 是你说的26*length的作法,结果大
数据超时了。这类型的题(比如word search),我都习惯用DFS+recursion,请问用
recursion解这类题是不是坏习惯?还有说BFS比DFS快,是general指所有这类型的题,
还是因为这道题求的是shortest transform, 所以能提前退出?
多谢!
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来,就要遍历hashtable 里所有的字。
: 这很不efficient,因为字典内可能含有很多字。还有就是,hashtable 遍历好像很不
: efficient,只有查询最适合。
: 倒过来思考:
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6,那么所有可能性就是 26*6 = 156,远远小于字典内的个数。
i*e
47 楼
Use StringBuilder when you want a mutable string.
Concatenating substrings is a very slow operation.
ie,
StringBuilder ww = new StringBuilder(str);
Then inside your loop use setCharAt() to modify the character at index j.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题,用的是一贯的DFS+recursion, 是你说的26*length的作法,结果大
: 数据超时了。这类型的题(比如word search),我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯?还有说BFS比DFS快,是general指所有这类型的题,
: 还是因为这道题求的是shortest transform, 所以能提前退出?
: 多谢!
Concatenating substrings is a very slow operation.
ie,
StringBuilder ww = new StringBuilder(str);
Then inside your loop use setCharAt() to modify the character at index j.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题,用的是一贯的DFS+recursion, 是你说的26*length的作法,结果大
: 数据超时了。这类型的题(比如word search),我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯?还有说BFS比DFS快,是general指所有这类型的题,
: 还是因为这道题求的是shortest transform, 所以能提前退出?
: 多谢!
i*e
48 楼
DFS will TLE in large tests, because it exhaust all possibilities.
BFS avoids this by finding only the shortest path.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题,用的是一贯的DFS+recursion, 是你说的26*length的作法,结果大
: 数据超时了。这类型的题(比如word search),我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯?还有说BFS比DFS快,是general指所有这类型的题,
: 还是因为这道题求的是shortest transform, 所以能提前退出?
: 多谢!
BFS avoids this by finding only the shortest path.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题,用的是一贯的DFS+recursion, 是你说的26*length的作法,结果大
: 数据超时了。这类型的题(比如word search),我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯?还有说BFS比DFS快,是general指所有这类型的题,
: 还是因为这道题求的是shortest transform, 所以能提前退出?
: 多谢!
h*y
50 楼
看不懂阿。
path和res的作用感觉有问题阿。。
) {
【在 c*****a 的大作中提到】
: 写了个java的第一题
: large的时间真长
: Run Status: Accepted!
: Program Runtime: 1460 milli secs
: import java.util.Set;
: import java.util.HashSet;
: import java.util.Hashtable;
: public class Solution {
: public int ladderLength(String start, String end, HashSet dict) {
: // Start typing your Java solution below
path和res的作用感觉有问题阿。。
) {
【在 c*****a 的大作中提到】
: 写了个java的第一题
: large的时间真长
: Run Status: Accepted!
: Program Runtime: 1460 milli secs
: import java.util.Set;
: import java.util.HashSet;
: import java.util.Hashtable;
: public class Solution {
: public int ladderLength(String start, String end, HashSet
: // Start typing your Java solution below
t*6
52 楼
第二题,求指导:
class Solution {
public:
void traverse(string& start, string& root, unordered_map string> >& prev, vector& current, vector>& result) {
auto iter = prev.find(root);
for (string str : iter->second) {
current.push_back(str);
if (str == start) {
vector new_one(current.size());
reverse_copy(current.begin(), current.end(), new_one.begin()
);
result.push_back(new_one);
} else {
traverse(start, str, prev, current, result);
}
current.pop_back();
}
}
vector> findLadders(string start, string end, unordered_
set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector S1;
vector S2;
S1.push_back(start);
unordered_map > prev;
bool found = false;
while(!S1.empty()) {
while(!S1.empty()) {
string current = S1.back();
S1.pop_back();
for (int i = 0; i < current.length(); ++i) {
for (int j = 0; j < 26; ++j) {
if ( 'a' + j != current[i] ) {
string now = current;
now[i] = 'a' + j;
if (now == end) found = true;
if (dict.find(now) != dict.end()) {
auto iter = prev.find(now);
if (iter == prev.end()) S2.push_back(now
);
prev[now].push_back(current);
}
}
}
}
}
if (found) break;
for (string s : S2) dict.erase(s);
swap(S1, S2);
}
vector > result;
vector current(1, end);
if (found) {
traverse(start, end, prev, current, result);
}
return result;
}
};
class Solution {
public:
void traverse(string& start, string& root, unordered_map
auto iter = prev.find(root);
for (string str : iter->second) {
current.push_back(str);
if (str == start) {
vector
reverse_copy(current.begin(), current.end(), new_one.begin()
);
result.push_back(new_one);
} else {
traverse(start, str, prev, current, result);
}
current.pop_back();
}
}
vector
set
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector
vector
S1.push_back(start);
unordered_map
bool found = false;
while(!S1.empty()) {
while(!S1.empty()) {
string current = S1.back();
S1.pop_back();
for (int i = 0; i < current.length(); ++i) {
for (int j = 0; j < 26; ++j) {
if ( 'a' + j != current[i] ) {
string now = current;
now[i] = 'a' + j;
if (now == end) found = true;
if (dict.find(now) != dict.end()) {
auto iter = prev.find(now);
if (iter == prev.end()) S2.push_back(now
);
prev[now].push_back(current);
}
}
}
}
}
if (found) break;
for (string s : S2) dict.erase(s);
swap(S1, S2);
}
vector
vector
if (found) {
traverse(start, end, prev, current, result);
}
return result;
}
};
c*t
53 楼
多谢!
第一题最后发现用 char array 比 StringBuilder还快
第二题又超时了,再求帮助!
用的是双queue解法,感觉比你和wwwyhs说的hashmap>用空间
更少,时间也应该更少,为啥又超呢?(唉,我为什么又说又)
public ArrayList> findLadders(String start, String end,
HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> ret = new ArrayList>(
);
int curr=1, next=0, count=1, n=start.length(), length=Integer.MAX_
VALUE;
LinkedList queue = new LinkedList();
queue.add(start);
LinkedList> pathQueue = new LinkedList String>>();
ArrayList path= new ArrayList();
path.add(start);
pathQueue.add(path);
while(!queue.isEmpty()){
String theWord = queue.poll();
char[] str = theWord.toCharArray();
curr--;
path=pathQueue.poll();
for(int j=0; j char och=str[j];
for(int i=0; i<26; i++){
char ch = (char) ('a'+i);
if(ch!=och){
str[j]=ch;
String word = new String(str);
if(word.equals(end)) {
length=count;
ArrayList newPath = new ArrayList >(path);
newPath.add(word);
ret.add(newPath);
}else if(dict.contains(word)){
queue.add(word);
ArrayList newPath = new ArrayList >(path);
newPath.add(word);
pathQueue.add(newPath);
next++;
}
str[j]=och;
}
}
}
if(curr==0){
count++;
if(count>length) return ret;
curr=next;
next=0;
}
}
return ret;
}
【在 i**********e 的大作中提到】
: DFS will TLE in large tests, because it exhaust all possibilities.
: BFS avoids this by finding only the shortest path.
第一题最后发现用 char array 比 StringBuilder还快
第二题又超时了,再求帮助!
用的是双queue解法,感觉比你和wwwyhs说的hashmap
更少,时间也应该更少,为啥又超呢?(唉,我为什么又说又)
public ArrayList
HashSet
// Start typing your Java solution below
// DO NOT write main() function
ArrayList
);
int curr=1, next=0, count=1, n=start.length(), length=Integer.MAX_
VALUE;
LinkedList
queue.add(start);
LinkedList
ArrayList
path.add(start);
pathQueue.add(path);
while(!queue.isEmpty()){
String theWord = queue.poll();
char[] str = theWord.toCharArray();
curr--;
path=pathQueue.poll();
for(int j=0; j
for(int i=0; i<26; i++){
char ch = (char) ('a'+i);
if(ch!=och){
str[j]=ch;
String word = new String(str);
if(word.equals(end)) {
length=count;
ArrayList
newPath.add(word);
ret.add(newPath);
}else if(dict.contains(word)){
queue.add(word);
ArrayList
newPath.add(word);
pathQueue.add(newPath);
next++;
}
str[j]=och;
}
}
}
if(curr==0){
count++;
if(count>length) return ret;
curr=next;
next=0;
}
}
return ret;
}
【在 i**********e 的大作中提到】
: DFS will TLE in large tests, because it exhaust all possibilities.
: BFS avoids this by finding only the shortest path.
p*e
54 楼
发个不用'a'-'z'的方法,第一题
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(start.size() != end.size()) return 0;
if(diff1(start, end)) return 2;
vector sq, eq, ms;
for(auto it = dict.begin(); it != dict.end(); ++it)
{
string s = *it;
if(s != start && s != end)
{
if(diff1(s, start))
sq.push_back(s);
else
ms.push_back(s);
}
}
eq.push_back(end);
int sizeofsq = sq.size();
int sizeofeq = eq.size();
if(sizeofsq == 0) return 0;
int beginofsq = 0, beginofeq = 0;
int step = 0;
int sizeofmap = ms.size(), nc = -1;
while(sizeofsq>beginofsq&&sizeofeq>beginofeq&&step sizeofmap!=nc)
{
step+=2;
for(int csq = beginofsq; csq {
string s = sq[csq];
for(int ceq = beginofeq; ceq {
if(diff1(s,eq[ceq]))
return step+1;
}
}
nc = sizeofmap;
sizeofmap = 0;
for(int j=0; j {
string m = ms[j];
bool b1 = false;
bool b2 = false;
for(int csq = beginofsq; csq {
if(diff1(m, sq[csq]))
{
b1 = true;
break;
}
}
for(int ceq = beginofeq; ceq {
if(diff1(m, eq[ceq]))
{
b2 = true;
break;
}
}
if(b1&&b2)
return step+2;
else if(b1)
sq.push_back(m);
else if(b2)
eq.push_back(m);
else
{
if(j != sizeofmap)
ms[sizeofmap] = m;
++sizeofmap;
}
}
beginofsq = sizeofsq;
sizeofsq = sq.size();
beginofeq = sizeofeq;
sizeofeq = eq.size();
}
return 0;
}
};
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(start.size() != end.size()) return 0;
if(diff1(start, end)) return 2;
vector
for(auto it = dict.begin(); it != dict.end(); ++it)
{
string s = *it;
if(s != start && s != end)
{
if(diff1(s, start))
sq.push_back(s);
else
ms.push_back(s);
}
}
eq.push_back(end);
int sizeofsq = sq.size();
int sizeofeq = eq.size();
if(sizeofsq == 0) return 0;
int beginofsq = 0, beginofeq = 0;
int step = 0;
int sizeofmap = ms.size(), nc = -1;
while(sizeofsq>beginofsq&&sizeofeq>beginofeq&&step
{
step+=2;
for(int csq = beginofsq; csq
string s = sq[csq];
for(int ceq = beginofeq; ceq
if(diff1(s,eq[ceq]))
return step+1;
}
}
nc = sizeofmap;
sizeofmap = 0;
for(int j=0; j
string m = ms[j];
bool b1 = false;
bool b2 = false;
for(int csq = beginofsq; csq
if(diff1(m, sq[csq]))
{
b1 = true;
break;
}
}
for(int ceq = beginofeq; ceq
if(diff1(m, eq[ceq]))
{
b2 = true;
break;
}
}
if(b1&&b2)
return step+2;
else if(b1)
sq.push_back(m);
else if(b2)
eq.push_back(m);
else
{
if(j != sizeofmap)
ms[sizeofmap] = m;
++sizeofmap;
}
}
beginofsq = sizeofsq;
sizeofsq = sq.size();
beginofeq = sizeofeq;
sizeofeq = eq.size();
}
return 0;
}
};
c*t
61 楼
看明白了.
1.遍历 构造map
2.由map, backtrack重建pathes
我模仿的写了一个java的,真的过了。1592ms
虽然双queue解法不需要backtracking,但TLE可能还是因为, 要往path queue里面存太
多path吧(每个node都要建一个path),读写太多了,而这个解法存的是edges(每个node
只用存parent nodes),读写少些。
【在 i**********e 的大作中提到】
: word ladder II 有人过了 large tests 吗?
: 我抛砖引玉一下吧,希望有大牛可以提出更好的解法。
: 思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下,果然简洁很多,
: 整个程序不到50行。
: 基于程序可读性,所以 bottom up 返回路径,产生了很多不必要的拷贝而导致效率会
: 差很多。但路径组合没那么多,所以性能上也没什么影响。
: typedef unordered_multimap Map;
: typedef pair PairIter;
: vector> findLadders(string start, string end, unordered_set<
: string> &dict) {
1.遍历 构造map
2.由map, backtrack重建pathes
我模仿的写了一个java的,真的过了。1592ms
虽然双queue解法不需要backtracking,但TLE可能还是因为, 要往path queue里面存太
多path吧(每个node都要建一个path),读写太多了,而这个解法存的是edges(每个node
只用存parent nodes),读写少些。
【在 i**********e 的大作中提到】
: word ladder II 有人过了 large tests 吗?
: 我抛砖引玉一下吧,希望有大牛可以提出更好的解法。
: 思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下,果然简洁很多,
: 整个程序不到50行。
: 基于程序可读性,所以 bottom up 返回路径,产生了很多不必要的拷贝而导致效率会
: 差很多。但路径组合没那么多,所以性能上也没什么影响。
: typedef unordered_multimap
: typedef pair
: vector
: string> &dict) {
f*t
63 楼
相当丑陋的BFS,已经尽量去除copy string的时间了,但还是超时,求指点T_T
class Path {
public:
Path() { path = new vector; }
~Path() { delete path; }
Path* duplicate() const {
Path *np = new Path;
np->path = new vector(*path);
return np;
}
vector *path;
};
class Solution {
public:
vector> findLadders(string start, string end, unordered_
set &dict) {
vector> ans;
queue q;
Path *np = new Path;
np->path->push_back(&start);
q.push(np);
unordered_set used;
queue levelUsed;
while (!q.empty()) {
int n = q.size();
while (n-- > 0) {
Path *p = q.front();
string temp(*p->path->back());
for (int i = 0; i < temp.size(); i++) {
char tc = temp[i];
for (int j = 0; j < 26; j++) {
if (tc == (char)('a' + j))
continue;
temp[i] = (char)('a' + j);
unordered_set::iterator it = dict.find(temp);
if (it != dict.end() && used.find(&(*it)) == used.
end()) {
np = p->duplicate();
np->path->push_back(&(*it));
if (temp == end) {
vector line;
for (vector::iterator itv =
np->path->begin(); itv != np->path->end(); itv++)
line.push_back(**itv);
ans.push_back(line);
}
q.push(np);
levelUsed.push(&(*it));
}
}
temp[i] = tc;
}
q.pop();
delete p;
}
if (!ans.empty())
break;
while(!levelUsed.empty()) {
used.insert(levelUsed.front());
levelUsed.pop();
}
}
return ans;
}
};
class Path {
public:
Path() { path = new vector
~Path() { delete path; }
Path* duplicate() const {
Path *np = new Path;
np->path = new vector
return np;
}
vector
};
class Solution {
public:
vector
set
vector
queue
Path *np = new Path;
np->path->push_back(&start);
q.push(np);
unordered_set
queue
while (!q.empty()) {
int n = q.size();
while (n-- > 0) {
Path *p = q.front();
string temp(*p->path->back());
for (int i = 0; i < temp.size(); i++) {
char tc = temp[i];
for (int j = 0; j < 26; j++) {
if (tc == (char)('a' + j))
continue;
temp[i] = (char)('a' + j);
unordered_set
if (it != dict.end() && used.find(&(*it)) == used.
end()) {
np = p->duplicate();
np->path->push_back(&(*it));
if (temp == end) {
vector
for (vector
np->path->begin(); itv != np->path->end(); itv++)
line.push_back(**itv);
ans.push_back(line);
}
q.push(np);
levelUsed.push(&(*it));
}
}
temp[i] = tc;
}
q.pop();
delete p;
}
if (!ans.empty())
break;
while(!levelUsed.empty()) {
used.insert(levelUsed.front());
levelUsed.pop();
}
}
return ans;
}
};
i*e
64 楼
我测试了你的程序,差不多4秒跑完所有test。
简单优化了一下变成3.5秒,还差1.5秒。
说说你duplicate 路径的时候怎么做的?
有把之前共享的路径也copy 下来了吗?
【在 f*******t 的大作中提到】
: 相当丑陋的BFS,已经尽量去除copy string的时间了,但还是超时,求指点T_T
: class Path {
: public:
: Path() { path = new vector; }
:
: ~Path() { delete path; }
:
: Path* duplicate() const {
: Path *np = new Path;
: np->path = new vector(*path);
简单优化了一下变成3.5秒,还差1.5秒。
说说你duplicate 路径的时候怎么做的?
有把之前共享的路径也copy 下来了吗?
【在 f*******t 的大作中提到】
: 相当丑陋的BFS,已经尽量去除copy string的时间了,但还是超时,求指点T_T
: class Path {
: public:
: Path() { path = new vector
:
: ~Path() { delete path; }
:
: Path* duplicate() const {
: Path *np = new Path;
: np->path = new vector
y*e
66 楼
DFS+pruning?
那步dict.erase()用的很妙
展开说说怎么想到的吧~
vector<
【在 t********6 的大作中提到】
: 第二题,求指导:
: class Solution {
: public:
: void traverse(string& start, string& root, unordered_map : string> >& prev, vector& current, vector>& result) {
: auto iter = prev.find(root);
: for (string str : iter->second) {
: current.push_back(str);
: if (str == start) {
: vector new_one(current.size());
那步dict.erase()用的很妙
展开说说怎么想到的吧~
vector<
【在 t********6 的大作中提到】
: 第二题,求指导:
: class Solution {
: public:
: void traverse(string& start, string& root, unordered_map
: auto iter = prev.find(root);
: for (string str : iter->second) {
: current.push_back(str);
: if (str == start) {
: vector
p*e
68 楼
rt
w*x
69 楼
这题怎么那么别扭,原来目标单词不在字典里...
还有我咋超时了...
还有我咋超时了...
i*e
70 楼
贴贴你代码?
w*x
71 楼
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
unordered_set visited;
visited.insert(start);
queue que;
que.push(start);
int nCurLev = 1;
int nCurNum = 1;
int nNextNum = 0;
while (!que.empty())
{
string strCur = que.front();
que.pop();
nCurNum--;
for (unordered_set::iterator it = dict.begin();
it != dict.end(); it++)
{
if (visited.find(*it) == visited.end() && canChng(*it,
strCur))
{
que.push(*it);
visited.insert(*it);
nNextNum++;
}
}
if (canChng(end, strCur))
return nCurLev+1;
if (nCurNum <= 0)
{
nCurLev++;
nCurNum = nNextNum;
nNextNum = 0;
}
}
return 0;
}
bool canChng(string a, string b)
{
if (a.length() != b.length())
return false;
bool bDiff = false;
for (int i = 0; i < a.length(); i++)
{
if (a.at(i) != b.at(i))
{
if (bDiff)
return false;
bDiff = true;
}
}
return bDiff;
}
};
public:
int ladderLength(string start, string end, unordered_set
unordered_set
visited.insert(start);
queue
que.push(start);
int nCurLev = 1;
int nCurNum = 1;
int nNextNum = 0;
while (!que.empty())
{
string strCur = que.front();
que.pop();
nCurNum--;
for (unordered_set
it != dict.end(); it++)
{
if (visited.find(*it) == visited.end() && canChng(*it,
strCur))
{
que.push(*it);
visited.insert(*it);
nNextNum++;
}
}
if (canChng(end, strCur))
return nCurLev+1;
if (nCurNum <= 0)
{
nCurLev++;
nCurNum = nNextNum;
nNextNum = 0;
}
}
return 0;
}
bool canChng(string a, string b)
{
if (a.length() != b.length())
return false;
bool bDiff = false;
for (int i = 0; i < a.length(); i++)
{
if (a.at(i) != b.at(i))
{
if (bDiff)
return false;
bDiff = true;
}
}
return bDiff;
}
};
i*e
72 楼
如果字典很大怎么办?
p*p
73 楼
large TLE了
不过ladder 1判断比较奇葩:hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
list queue;
set visited;
map stepMap;
queue.push_back(start);
visited.insert(start);
stepMap[start] = 1;
while (!queue.empty()) {
string s = queue.front();
queue.pop_front();
if (diffByOne(s, end)) return stepMap[s] + 1;
int currentStep = stepMap[s];
for (string strInDict : dict) {
if (visited.find(strInDict) != visited.end()) continue;
if (diffByOne(s, strInDict)) {
queue.push_back(strInDict);
visited.insert(strInDict);
stepMap[strInDict] = currentStep + 1;
}
}
}
return 0;
}
bool diffByOne(string &s1, string &s2) {
if (s1.size() != s2.size()) return false;
int diff = 0;
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) ++diff;
if (diff > 1) return false;
}
return diff == 1 ? true : false;
}
};
不过ladder 1判断比较奇葩:hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
class Solution {
public:
int ladderLength(string start, string end, unordered_set
// Start typing your C/C++ solution below
// DO NOT write int main() function
list
set
map
queue.push_back(start);
visited.insert(start);
stepMap[start] = 1;
while (!queue.empty()) {
string s = queue.front();
queue.pop_front();
if (diffByOne(s, end)) return stepMap[s] + 1;
int currentStep = stepMap[s];
for (string strInDict : dict) {
if (visited.find(strInDict) != visited.end()) continue;
if (diffByOne(s, strInDict)) {
queue.push_back(strInDict);
visited.insert(strInDict);
stepMap[strInDict] = currentStep + 1;
}
}
}
return 0;
}
bool diffByOne(string &s1, string &s2) {
if (s1.size() != s2.size()) return false;
int diff = 0;
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) ++diff;
if (diff > 1) return false;
}
return diff == 1 ? true : false;
}
};
i*e
74 楼
关于怎么测下一步是不是合法:
每一个字母'a'-'z'遍历,再看是否在字典里的复杂度 = 26 * n (n = 字的长度)
unordered_set 的查询是 O(1) 的。
遍历所有字典里的字然后一个一个比较是 n * dictionary_size,复杂度自然就上去
了。
每一个字母'a'-'z'遍历,再看是否在字典里的复杂度 = 26 * n (n = 字的长度)
unordered_set 的查询是 O(1) 的。
遍历所有字典里的字然后一个一个比较是 n * dictionary_size,复杂度自然就上去
了。
a*o
75 楼
我来贴个能过的,比较丑,大家见谅...
int ladderLength(string start, string end, tr1::unordered_set &dict)
{
set contain;
int count = 1;
queue list[2];
list[0].push(start);
while (list[0].size()!= 0 || list[1].size()!=0){
int oldlist = 0;
int newlist = 1;
if (list[0].size()== 0){
oldlist = 1;
newlist = 0;
}
while (list[oldlist].size() != 0){
string curr = list[oldlist].front();
list[oldlist].pop();
if (contain.count(curr) > 0) continue;
contain.insert(curr);
for (int i = 0; i< curr.size(); i++){
for (int j = 0; j<26; j++){
char temp = curr[i];
char newtemp = (char) ('a'+j);
if (temp != newtemp){
string newcurr = curr;
newcurr[i] = newtemp;
if (newcurr == end) return count
+1;
if (dict.count(newcurr)> 0){
list[newlist].push(
newcurr);
}
}
}
}
}
count ++;
}
return 0;
}
【在 p****e 的大作中提到】
: rt
int ladderLength(string start, string end, tr1::unordered_set
{
set
int count = 1;
queue
list[0].push(start);
while (list[0].size()!= 0 || list[1].size()!=0){
int oldlist = 0;
int newlist = 1;
if (list[0].size()== 0){
oldlist = 1;
newlist = 0;
}
while (list[oldlist].size() != 0){
string curr = list[oldlist].front();
list[oldlist].pop();
if (contain.count(curr) > 0) continue;
contain.insert(curr);
for (int i = 0; i< curr.size(); i++){
for (int j = 0; j<26; j++){
char temp = curr[i];
char newtemp = (char) ('a'+j);
if (temp != newtemp){
string newcurr = curr;
newcurr[i] = newtemp;
if (newcurr == end) return count
+1;
if (dict.count(newcurr)> 0){
list[newlist].push(
newcurr);
}
}
}
}
}
count ++;
}
return 0;
}
【在 p****e 的大作中提到】
: rt
w*x
76 楼
) {
这个也超时了
【在 p*****p 的大作中提到】
: large TLE了
: 不过ladder 1判断比较奇葩:hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
: class Solution {
: public:
: int ladderLength(string start, string end, unordered_set
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: list
: set
: map
i*e
77 楼
是比较奇怪,但仔细看好规则:
Each intermediate word must exist in the dictionary
start 和 end 都不是 intermediate word,所以字典可有可无。
) {
【在 p*****p 的大作中提到】
: large TLE了
: 不过ladder 1判断比较奇葩:hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
: class Solution {
: public:
: int ladderLength(string start, string end, unordered_set &dict) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: list queue;
: set visited;
: map stepMap;
Each intermediate word must exist in the dictionary
start 和 end 都不是 intermediate word,所以字典可有可无。
) {
【在 p*****p 的大作中提到】
: large TLE了
: 不过ladder 1判断比较奇葩:hot, hot, ["dot"]那个不是0而是hot->dot->hot是3……
: class Solution {
: public:
: int ladderLength(string start, string end, unordered_set
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: list
: set
: map
i*e
91 楼
你要的是 unordered_multimap 吧。
一个 key 可以 map 到好几个 value.
一个 key 可以 map 到好几个 value.
f*t
93 楼
public int ladderLength(String start, String end, HashSet dict) {
if (start == null || end == null || start.length() != end.length())
return 0;
int dist = 1;
HashSet used = new HashSet();
HashSet cur = new HashSet();
cur.add(start);
while(!cur.isEmpty()) {
HashSet newCur = new HashSet();
dist++;
for (String s : cur) {
char[] str = s.toCharArray();
for (int i = 0; i < str.length; i++) {
for (int j = 0; j < 26; j++) {
if (str[i] != (char)('a' + j)) {
char temp = str[i];
str[i] = (char)('a' + j);
String candidate = new String(str);
if (candidate.equals(end))
return dist;
if (!used.contains(candidate) && dict.contains(
candidate)) {
newCur.add(candidate);
used.add(candidate);
}
str[i] = temp;
}
}
}
}
cur = newCur;
}
return 0;
}
if (start == null || end == null || start.length() != end.length())
return 0;
int dist = 1;
HashSet
HashSet
cur.add(start);
while(!cur.isEmpty()) {
HashSet
dist++;
for (String s : cur) {
char[] str = s.toCharArray();
for (int i = 0; i < str.length; i++) {
for (int j = 0; j < 26; j++) {
if (str[i] != (char)('a' + j)) {
char temp = str[i];
str[i] = (char)('a' + j);
String candidate = new String(str);
if (candidate.equals(end))
return dist;
if (!used.contains(candidate) && dict.contains(
candidate)) {
newCur.add(candidate);
used.add(candidate);
}
str[i] = temp;
}
}
}
}
cur = newCur;
}
return 0;
}
b*u
94 楼
从两头往中间BFS,还能快点
x*6
95 楼
牛啊,等着leetcode刷新题。。。
g*9
97 楼
写了一个能过大数据test的C++版本,回馈版友了
大家见笑了。。
单纯的建立图,再暴力BFS确实过不了大数据的,平方复杂度在大数据时立刻超时
class Solution {
public:
int dis(const string& a, const string& b) {
int n = a.size();
if (n != b.size()) {
return -1;
}
int diff = 0;
int i;
for (i = 0; i < a.size(); i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 1) {
return -1;
}
}
} // for
return diff;
}
void gen(const string& s, vector & v) {
v.clear();
int n = s.size();
string scopy;
char c;
int i;
for (i = 0; i < n; i++) {
scopy = s;
for (c = 'a'; c <= 'z'; c++) {
if (s[i] != c) {
scopy[i] = c;
v.push_back(scopy);
}
}
}
return;
}
int ladderLength(string start, string end, unordered_set &dict) {
int n = start.size();
if (n != end.size()) {
return 0;
}
unordered_set::iterator it;
unordered_map visited;
unordered_map::iterator mt;
for (it = dict.begin(); it != dict.end(); it++) {
visited[*it] = 0;
}
visited[start] = 1;
deque q;
q.push_back(start);
string k, c;
vector can;
int i;
while (1) {
if (q.empty()) {
return 0;
}
k = q.front();
q.pop_front();
gen(k, can);
for (i = 0; i < can.size(); i++) {
string & w = can[i];
mt = visited.find(w);
if (mt != visited.end() &&
(mt->second == 0 || w == end)) {
q.push_back(w);
mt->second = visited[k] + 1;
if (w == end) {
return mt->second;
}
}
}
} // while
return 0;
}
};
大家见笑了。。
单纯的建立图,再暴力BFS确实过不了大数据的,平方复杂度在大数据时立刻超时
class Solution {
public:
int dis(const string& a, const string& b) {
int n = a.size();
if (n != b.size()) {
return -1;
}
int diff = 0;
int i;
for (i = 0; i < a.size(); i++) {
if (a[i] != b[i]) {
diff++;
if (diff > 1) {
return -1;
}
}
} // for
return diff;
}
void gen(const string& s, vector
v.clear();
int n = s.size();
string scopy;
char c;
int i;
for (i = 0; i < n; i++) {
scopy = s;
for (c = 'a'; c <= 'z'; c++) {
if (s[i] != c) {
scopy[i] = c;
v.push_back(scopy);
}
}
}
return;
}
int ladderLength(string start, string end, unordered_set
int n = start.size();
if (n != end.size()) {
return 0;
}
unordered_set
unordered_map
unordered_map
for (it = dict.begin(); it != dict.end(); it++) {
visited[*it] = 0;
}
visited[start] = 1;
deque
q.push_back(start);
string k, c;
vector
int i;
while (1) {
if (q.empty()) {
return 0;
}
k = q.front();
q.pop_front();
gen(k, can);
for (i = 0; i < can.size(); i++) {
string & w = can[i];
mt = visited.find(w);
if (mt != visited.end() &&
(mt->second == 0 || w == end)) {
q.push_back(w);
mt->second = visited[k] + 1;
if (w == end) {
return mt->second;
}
}
}
} // while
return 0;
}
};
d*g
98 楼
第二题要过大集合还真不容易。。。
c*a
99 楼
写了个java的第一题
large的时间真长
Run Status: Accepted!
Program Runtime: 1460 milli secs
import java.util.Set;
import java.util.HashSet;
import java.util.Hashtable;
public class Solution {
public int ladderLength(String start, String end, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
Queue queue = new LinkedList();
Set visited = new HashSet();
Hashtable path = new Hashtable();
List res = new ArrayList();
queue.add(start);
visited.add(start);
while(queue.size()>0){
String prev = queue.poll();
for(String curr: generate(prev, dict)){
if(curr.equals(end)){
res.add(end);
while(prev!=null){
res.add(0,prev);
prev = path.get(prev);
}
return res.size();
}
if(!visited.contains(curr)){
visited.add(curr);
queue.add(curr);
path.put(curr, prev);
}
}
}
return 0;
}
public Set generate(String s, HashSet dict){
Set words = new HashSet();
for(int i =0;i for(char j = 'a'; j<='z';j++){
char[] chs = s.toCharArray();
if(chs[i]!=j ){
chs[i] = j;
String ns = new String(chs);
if(dict.contains(ns))
words.add(ns);
}
}
}
return words;
}
}
large的时间真长
Run Status: Accepted!
Program Runtime: 1460 milli secs
import java.util.Set;
import java.util.HashSet;
import java.util.Hashtable;
public class Solution {
public int ladderLength(String start, String end, HashSet
// Start typing your Java solution below
// DO NOT write main() function
Queue
Set
Hashtable
List
queue.add(start);
visited.add(start);
while(queue.size()>0){
String prev = queue.poll();
for(String curr: generate(prev, dict)){
if(curr.equals(end)){
res.add(end);
while(prev!=null){
res.add(0,prev);
prev = path.get(prev);
}
return res.size();
}
if(!visited.contains(curr)){
visited.add(curr);
queue.add(curr);
path.put(curr, prev);
}
}
}
return 0;
}
public Set
Set
for(int i =0;i
char[] chs = s.toCharArray();
if(chs[i]!=j ){
chs[i] = j;
String ns = new String(chs);
if(dict.contains(ns))
words.add(ns);
}
}
}
return words;
}
}
i*e
100 楼
word ladder II 有人过了 large tests 吗?
我抛砖引玉一下吧,希望有大牛可以提出更好的解法。
思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下,果然简洁很多,
整个程序不到50行。
基于程序可读性,所以 bottom up 返回路径,产生了很多不必要的拷贝而导致效率会
差很多。但路径组合没那么多,所以性能上也没什么影响。
typedef unordered_multimap Map;
typedef pair PairIter;
vector> findLadders(string start, string end, unordered_set<
string> &dict) {
Map map, map2;
queue q, q2;
q.push(start);
bool goal = false;
while (!q.empty()) {
string word = q.front();
q.pop();
for (int i = 0; i < start.length(); i++) {
string s = word;
for (char c = 'a'; c <= 'z'; c++) {
s[i] = c;
if (s == word) continue;
if (s == end) goal = true;
if (map.find(s) == map.end() && dict.find(s) != dict.end()) {
if (map2.find(s) == map2.end()) {
q2.push(s);
}
map2.insert(make_pair(s, word));
}
}
}
if (q.empty()) {
swap(q, q2);
map.insert(map2.begin(), map2.end());
map2.clear();
if (goal) return print(map, end, start);
}
}
return vector>();
}
// backtrack to reconstruct the path from start -> end.
vector> print(Map &map, string s, string start, int depth = 0
) {
if (depth > 0 && s == start) {
return vector>(1, vector(1, s));
}
vector> ret;
for (PairIter it = map.equal_range(s); it.first != it.second; ++it.first
) {
vector> temp = print(map, it.first->second, start,
depth+1);
for (int i = 0; i < temp.size(); i++) {
temp[i].push_back(s);
}
ret.insert(ret.end(), temp.begin(), temp.end());
}
return ret;
}
我抛砖引玉一下吧,希望有大牛可以提出更好的解法。
思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下,果然简洁很多,
整个程序不到50行。
基于程序可读性,所以 bottom up 返回路径,产生了很多不必要的拷贝而导致效率会
差很多。但路径组合没那么多,所以性能上也没什么影响。
typedef unordered_multimap
typedef pair
vector
string> &dict) {
Map map, map2;
queue
q.push(start);
bool goal = false;
while (!q.empty()) {
string word = q.front();
q.pop();
for (int i = 0; i < start.length(); i++) {
string s = word;
for (char c = 'a'; c <= 'z'; c++) {
s[i] = c;
if (s == word) continue;
if (s == end) goal = true;
if (map.find(s) == map.end() && dict.find(s) != dict.end()) {
if (map2.find(s) == map2.end()) {
q2.push(s);
}
map2.insert(make_pair(s, word));
}
}
}
if (q.empty()) {
swap(q, q2);
map.insert(map2.begin(), map2.end());
map2.clear();
if (goal) return print(map, end, start);
}
}
return vector
}
// backtrack to reconstruct the path from start -> end.
vector
) {
if (depth > 0 && s == start) {
return vector
}
vector
for (PairIter it = map.equal_range(s); it.first != it.second; ++it.first
) {
vector
depth+1);
for (int i = 0; i < temp.size(); i++) {
temp[i].push_back(s);
}
ret.insert(ret.end(), temp.begin(), temp.end());
}
return ret;
}
d*e
101 楼
贴个第一题,
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
queue q;
queue cnt;
unordered_set visited;
q.push(start);
cnt.push(1);
if (start != end) visited.insert(start);
while (!q.empty()) {
string word = q.front(); q.pop();
int dist = cnt.front(); cnt.pop();
if (dist > 1 && word == end) return dist;
for (int i = 0; i < word.size(); i++) {
string copy(word);
for (char c = 'a'; c <= 'z'; c++)
if (c != word[i]) {
copy[i] = c;
if (dict.find(copy) != dict.end() &&
visited.find(copy) == visited.end()) {
q.push(copy);
cnt.push(dist+1);
visited.insert(copy);
}
}
}
}
return 0;
}
};
【在 p****e 的大作中提到】
: rt
class Solution {
public:
int ladderLength(string start, string end, unordered_set
queue
queue
unordered_set
q.push(start);
cnt.push(1);
if (start != end) visited.insert(start);
while (!q.empty()) {
string word = q.front(); q.pop();
int dist = cnt.front(); cnt.pop();
if (dist > 1 && word == end) return dist;
for (int i = 0; i < word.size(); i++) {
string copy(word);
for (char c = 'a'; c <= 'z'; c++)
if (c != word[i]) {
copy[i] = c;
if (dict.find(copy) != dict.end() &&
visited.find(copy) == visited.end()) {
q.push(copy);
cnt.push(dist+1);
visited.insert(copy);
}
}
}
}
return 0;
}
};
【在 p****e 的大作中提到】
: rt
w*t
102 楼
career 150上有这个题,解法就是 BFS + hashmap存路径,算是标准的解法把。
j*g
103 楼
第二个过了Large的 轻拍
class Solution {
public:
vector> findLadders(string start, string end, unordered_
set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=dict.size();
int res=1;
int done=0;
stack stk[2];
unordered_set used;
unordered_map > path;
unordered_set level;
int index=0;
stk[index%2].push(start);
used.insert(start);
vector> rtn;
while(!stk[index%2].empty()&&done!=2){
if(res == size+2)
return rtn;
string current=stk[index%2].top();
stk[index%2].pop();
int N=current.length();
for(int i=0;i for(char s='a';s<='z';s++){
if(current[i]!=s){
string tmp = current;
tmp[i]=s;
if(dict.find(tmp)!=dict.end()||!tmp.compare(end)){
if(path.find(tmp)==path.end()){
path[tmp]=vector (1,current);
level.insert(tmp);
}else{
if(level.find(tmp)!=level.end())
path[tmp].push_back(current);
}
if(!tmp.compare(end))
done=1;
else if(used.find(tmp)==used.end()){
stk[(index+1)%2].push(tmp);
used.insert(tmp);
}
}
}
}
}
if(stk[index%2].empty()){
index=index+1;
res++;
level.clear();
if(done)
done=2;
}
}
if(done)
getpath(start, end, path, rtn, vector(0,"a"));
return rtn;
}
void getpath(string start, string end, unordered_map string> > &path, vector > &rtn, vector route){
if(!start.compare(end)&&route.size()!=0){
route.push_back(end);
reverse(route.begin(), route.end());
rtn.push_back(route);
return;
}
vector up = path[end];
route.push_back(end);
for(int i=0; i getpath(start, up[i], path, rtn, route);
}
}
};
class Solution {
public:
vector
set
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size=dict.size();
int res=1;
int done=0;
stack
unordered_set
unordered_map
unordered_set
int index=0;
stk[index%2].push(start);
used.insert(start);
vector
while(!stk[index%2].empty()&&done!=2){
if(res == size+2)
return rtn;
string current=stk[index%2].top();
stk[index%2].pop();
int N=current.length();
for(int i=0;i
if(current[i]!=s){
string tmp = current;
tmp[i]=s;
if(dict.find(tmp)!=dict.end()||!tmp.compare(end)){
if(path.find(tmp)==path.end()){
path[tmp]=vector
level.insert(tmp);
}else{
if(level.find(tmp)!=level.end())
path[tmp].push_back(current);
}
if(!tmp.compare(end))
done=1;
else if(used.find(tmp)==used.end()){
stk[(index+1)%2].push(tmp);
used.insert(tmp);
}
}
}
}
}
if(stk[index%2].empty()){
index=index+1;
res++;
level.clear();
if(done)
done=2;
}
}
if(done)
getpath(start, end, path, rtn, vector
return rtn;
}
void getpath(string start, string end, unordered_map
if(!start.compare(end)&&route.size()!=0){
route.push_back(end);
reverse(route.begin(), route.end());
rtn.push_back(route);
return;
}
vector
route.push_back(end);
for(int i=0; i
}
}
};
c*t
104 楼
大侠。
我刚开始做第一题,用的是一贯的DFS+recursion, 是你说的26*length的作法,结果大
数据超时了。这类型的题(比如word search),我都习惯用DFS+recursion,请问用
recursion解这类题是不是坏习惯?还有说BFS比DFS快,是general指所有这类型的题,
还是因为这道题求的是shortest transform, 所以能提前退出?
多谢!
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来,就要遍历hashtable 里所有的字。
: 这很不efficient,因为字典内可能含有很多字。还有就是,hashtable 遍历好像很不
: efficient,只有查询最适合。
: 倒过来思考:
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6,那么所有可能性就是 26*6 = 156,远远小于字典内的个数。
我刚开始做第一题,用的是一贯的DFS+recursion, 是你说的26*length的作法,结果大
数据超时了。这类型的题(比如word search),我都习惯用DFS+recursion,请问用
recursion解这类题是不是坏习惯?还有说BFS比DFS快,是general指所有这类型的题,
还是因为这道题求的是shortest transform, 所以能提前退出?
多谢!
【在 i**********e 的大作中提到】
: 你的算法每次从queue 里取出一个字出来,就要遍历hashtable 里所有的字。
: 这很不efficient,因为字典内可能含有很多字。还有就是,hashtable 遍历好像很不
: efficient,只有查询最适合。
: 倒过来思考:
: 把queue 取出来的那个字的所有可能性枚举出来。
: 如果字的长度是6,那么所有可能性就是 26*6 = 156,远远小于字典内的个数。
i*e
105 楼
Use StringBuilder when you want a mutable string.
Concatenating substrings is a very slow operation.
ie,
StringBuilder ww = new StringBuilder(str);
Then inside your loop use setCharAt() to modify the character at index j.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题,用的是一贯的DFS+recursion, 是你说的26*length的作法,结果大
: 数据超时了。这类型的题(比如word search),我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯?还有说BFS比DFS快,是general指所有这类型的题,
: 还是因为这道题求的是shortest transform, 所以能提前退出?
: 多谢!
Concatenating substrings is a very slow operation.
ie,
StringBuilder ww = new StringBuilder(str);
Then inside your loop use setCharAt() to modify the character at index j.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题,用的是一贯的DFS+recursion, 是你说的26*length的作法,结果大
: 数据超时了。这类型的题(比如word search),我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯?还有说BFS比DFS快,是general指所有这类型的题,
: 还是因为这道题求的是shortest transform, 所以能提前退出?
: 多谢!
i*e
106 楼
DFS will TLE in large tests, because it exhaust all possibilities.
BFS avoids this by finding only the shortest path.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题,用的是一贯的DFS+recursion, 是你说的26*length的作法,结果大
: 数据超时了。这类型的题(比如word search),我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯?还有说BFS比DFS快,是general指所有这类型的题,
: 还是因为这道题求的是shortest transform, 所以能提前退出?
: 多谢!
BFS avoids this by finding only the shortest path.
【在 c********t 的大作中提到】
: 大侠。
: 我刚开始做第一题,用的是一贯的DFS+recursion, 是你说的26*length的作法,结果大
: 数据超时了。这类型的题(比如word search),我都习惯用DFS+recursion,请问用
: recursion解这类题是不是坏习惯?还有说BFS比DFS快,是general指所有这类型的题,
: 还是因为这道题求的是shortest transform, 所以能提前退出?
: 多谢!
h*y
108 楼
看不懂阿。
path和res的作用感觉有问题阿。。
) {
【在 c*****a 的大作中提到】
: 写了个java的第一题
: large的时间真长
: Run Status: Accepted!
: Program Runtime: 1460 milli secs
: import java.util.Set;
: import java.util.HashSet;
: import java.util.Hashtable;
: public class Solution {
: public int ladderLength(String start, String end, HashSet dict) {
: // Start typing your Java solution below
path和res的作用感觉有问题阿。。
) {
【在 c*****a 的大作中提到】
: 写了个java的第一题
: large的时间真长
: Run Status: Accepted!
: Program Runtime: 1460 milli secs
: import java.util.Set;
: import java.util.HashSet;
: import java.util.Hashtable;
: public class Solution {
: public int ladderLength(String start, String end, HashSet
: // Start typing your Java solution below
t*6
110 楼
第二题,求指导:
class Solution {
public:
void traverse(string& start, string& root, unordered_map string> >& prev, vector& current, vector>& result) {
auto iter = prev.find(root);
for (string str : iter->second) {
current.push_back(str);
if (str == start) {
vector new_one(current.size());
reverse_copy(current.begin(), current.end(), new_one.begin()
);
result.push_back(new_one);
} else {
traverse(start, str, prev, current, result);
}
current.pop_back();
}
}
vector> findLadders(string start, string end, unordered_
set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector S1;
vector S2;
S1.push_back(start);
unordered_map > prev;
bool found = false;
while(!S1.empty()) {
while(!S1.empty()) {
string current = S1.back();
S1.pop_back();
for (int i = 0; i < current.length(); ++i) {
for (int j = 0; j < 26; ++j) {
if ( 'a' + j != current[i] ) {
string now = current;
now[i] = 'a' + j;
if (now == end) found = true;
if (dict.find(now) != dict.end()) {
auto iter = prev.find(now);
if (iter == prev.end()) S2.push_back(now
);
prev[now].push_back(current);
}
}
}
}
}
if (found) break;
for (string s : S2) dict.erase(s);
swap(S1, S2);
}
vector > result;
vector current(1, end);
if (found) {
traverse(start, end, prev, current, result);
}
return result;
}
};
class Solution {
public:
void traverse(string& start, string& root, unordered_map
auto iter = prev.find(root);
for (string str : iter->second) {
current.push_back(str);
if (str == start) {
vector
reverse_copy(current.begin(), current.end(), new_one.begin()
);
result.push_back(new_one);
} else {
traverse(start, str, prev, current, result);
}
current.pop_back();
}
}
vector
set
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector
vector
S1.push_back(start);
unordered_map
bool found = false;
while(!S1.empty()) {
while(!S1.empty()) {
string current = S1.back();
S1.pop_back();
for (int i = 0; i < current.length(); ++i) {
for (int j = 0; j < 26; ++j) {
if ( 'a' + j != current[i] ) {
string now = current;
now[i] = 'a' + j;
if (now == end) found = true;
if (dict.find(now) != dict.end()) {
auto iter = prev.find(now);
if (iter == prev.end()) S2.push_back(now
);
prev[now].push_back(current);
}
}
}
}
}
if (found) break;
for (string s : S2) dict.erase(s);
swap(S1, S2);
}
vector
vector
if (found) {
traverse(start, end, prev, current, result);
}
return result;
}
};
c*t
111 楼
多谢!
第一题最后发现用 char array 比 StringBuilder还快
第二题又超时了,再求帮助!
用的是双queue解法,感觉比你和wwwyhs说的hashmap>用空间
更少,时间也应该更少,为啥又超呢?(唉,我为什么又说又)
public ArrayList> findLadders(String start, String end,
HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> ret = new ArrayList>(
);
int curr=1, next=0, count=1, n=start.length(), length=Integer.MAX_
VALUE;
LinkedList queue = new LinkedList();
queue.add(start);
LinkedList> pathQueue = new LinkedList String>>();
ArrayList path= new ArrayList();
path.add(start);
pathQueue.add(path);
while(!queue.isEmpty()){
String theWord = queue.poll();
char[] str = theWord.toCharArray();
curr--;
path=pathQueue.poll();
for(int j=0; j char och=str[j];
for(int i=0; i<26; i++){
char ch = (char) ('a'+i);
if(ch!=och){
str[j]=ch;
String word = new String(str);
if(word.equals(end)) {
length=count;
ArrayList newPath = new ArrayList >(path);
newPath.add(word);
ret.add(newPath);
}else if(dict.contains(word)){
queue.add(word);
ArrayList newPath = new ArrayList >(path);
newPath.add(word);
pathQueue.add(newPath);
next++;
}
str[j]=och;
}
}
}
if(curr==0){
count++;
if(count>length) return ret;
curr=next;
next=0;
}
}
return ret;
}
【在 i**********e 的大作中提到】
: DFS will TLE in large tests, because it exhaust all possibilities.
: BFS avoids this by finding only the shortest path.
第一题最后发现用 char array 比 StringBuilder还快
第二题又超时了,再求帮助!
用的是双queue解法,感觉比你和wwwyhs说的hashmap
更少,时间也应该更少,为啥又超呢?(唉,我为什么又说又)
public ArrayList
HashSet
// Start typing your Java solution below
// DO NOT write main() function
ArrayList
);
int curr=1, next=0, count=1, n=start.length(), length=Integer.MAX_
VALUE;
LinkedList
queue.add(start);
LinkedList
ArrayList
path.add(start);
pathQueue.add(path);
while(!queue.isEmpty()){
String theWord = queue.poll();
char[] str = theWord.toCharArray();
curr--;
path=pathQueue.poll();
for(int j=0; j
for(int i=0; i<26; i++){
char ch = (char) ('a'+i);
if(ch!=och){
str[j]=ch;
String word = new String(str);
if(word.equals(end)) {
length=count;
ArrayList
newPath.add(word);
ret.add(newPath);
}else if(dict.contains(word)){
queue.add(word);
ArrayList
newPath.add(word);
pathQueue.add(newPath);
next++;
}
str[j]=och;
}
}
}
if(curr==0){
count++;
if(count>length) return ret;
curr=next;
next=0;
}
}
return ret;
}
【在 i**********e 的大作中提到】
: DFS will TLE in large tests, because it exhaust all possibilities.
: BFS avoids this by finding only the shortest path.
p*e
112 楼
发个不用'a'-'z'的方法,第一题
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(start.size() != end.size()) return 0;
if(diff1(start, end)) return 2;
vector sq, eq, ms;
for(auto it = dict.begin(); it != dict.end(); ++it)
{
string s = *it;
if(s != start && s != end)
{
if(diff1(s, start))
sq.push_back(s);
else
ms.push_back(s);
}
}
eq.push_back(end);
int sizeofsq = sq.size();
int sizeofeq = eq.size();
if(sizeofsq == 0) return 0;
int beginofsq = 0, beginofeq = 0;
int step = 0;
int sizeofmap = ms.size(), nc = -1;
while(sizeofsq>beginofsq&&sizeofeq>beginofeq&&step sizeofmap!=nc)
{
step+=2;
for(int csq = beginofsq; csq {
string s = sq[csq];
for(int ceq = beginofeq; ceq {
if(diff1(s,eq[ceq]))
return step+1;
}
}
nc = sizeofmap;
sizeofmap = 0;
for(int j=0; j {
string m = ms[j];
bool b1 = false;
bool b2 = false;
for(int csq = beginofsq; csq {
if(diff1(m, sq[csq]))
{
b1 = true;
break;
}
}
for(int ceq = beginofeq; ceq {
if(diff1(m, eq[ceq]))
{
b2 = true;
break;
}
}
if(b1&&b2)
return step+2;
else if(b1)
sq.push_back(m);
else if(b2)
eq.push_back(m);
else
{
if(j != sizeofmap)
ms[sizeofmap] = m;
++sizeofmap;
}
}
beginofsq = sizeofsq;
sizeofsq = sq.size();
beginofeq = sizeofeq;
sizeofeq = eq.size();
}
return 0;
}
};
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(start.size() != end.size()) return 0;
if(diff1(start, end)) return 2;
vector
for(auto it = dict.begin(); it != dict.end(); ++it)
{
string s = *it;
if(s != start && s != end)
{
if(diff1(s, start))
sq.push_back(s);
else
ms.push_back(s);
}
}
eq.push_back(end);
int sizeofsq = sq.size();
int sizeofeq = eq.size();
if(sizeofsq == 0) return 0;
int beginofsq = 0, beginofeq = 0;
int step = 0;
int sizeofmap = ms.size(), nc = -1;
while(sizeofsq>beginofsq&&sizeofeq>beginofeq&&step
{
step+=2;
for(int csq = beginofsq; csq
string s = sq[csq];
for(int ceq = beginofeq; ceq
if(diff1(s,eq[ceq]))
return step+1;
}
}
nc = sizeofmap;
sizeofmap = 0;
for(int j=0; j
string m = ms[j];
bool b1 = false;
bool b2 = false;
for(int csq = beginofsq; csq
if(diff1(m, sq[csq]))
{
b1 = true;
break;
}
}
for(int ceq = beginofeq; ceq
if(diff1(m, eq[ceq]))
{
b2 = true;
break;
}
}
if(b1&&b2)
return step+2;
else if(b1)
sq.push_back(m);
else if(b2)
eq.push_back(m);
else
{
if(j != sizeofmap)
ms[sizeofmap] = m;
++sizeofmap;
}
}
beginofsq = sizeofsq;
sizeofsq = sq.size();
beginofeq = sizeofeq;
sizeofeq = eq.size();
}
return 0;
}
};
c*t
119 楼
看明白了.
1.遍历 构造map
2.由map, backtrack重建pathes
我模仿的写了一个java的,真的过了。1592ms
虽然双queue解法不需要backtracking,但TLE可能还是因为, 要往path queue里面存太
多path吧(每个node都要建一个path),读写太多了,而这个解法存的是edges(每个node
只用存parent nodes),读写少些。
【在 i**********e 的大作中提到】
: word ladder II 有人过了 large tests 吗?
: 我抛砖引玉一下吧,希望有大牛可以提出更好的解法。
: 思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下,果然简洁很多,
: 整个程序不到50行。
: 基于程序可读性,所以 bottom up 返回路径,产生了很多不必要的拷贝而导致效率会
: 差很多。但路径组合没那么多,所以性能上也没什么影响。
: typedef unordered_multimap Map;
: typedef pair PairIter;
: vector> findLadders(string start, string end, unordered_set<
: string> &dict) {
1.遍历 构造map
2.由map, backtrack重建pathes
我模仿的写了一个java的,真的过了。1592ms
虽然双queue解法不需要backtracking,但TLE可能还是因为, 要往path queue里面存太
多path吧(每个node都要建一个path),读写太多了,而这个解法存的是edges(每个node
只用存parent nodes),读写少些。
【在 i**********e 的大作中提到】
: word ladder II 有人过了 large tests 吗?
: 我抛砖引玉一下吧,希望有大牛可以提出更好的解法。
: 思路就是按照 wwwyhx 的思路 backtrack 重建路径。昨晚写了一下,果然简洁很多,
: 整个程序不到50行。
: 基于程序可读性,所以 bottom up 返回路径,产生了很多不必要的拷贝而导致效率会
: 差很多。但路径组合没那么多,所以性能上也没什么影响。
: typedef unordered_multimap
: typedef pair
: vector
: string> &dict) {
f*t
121 楼
相当丑陋的BFS,已经尽量去除copy string的时间了,但还是超时,求指点T_T
class Path {
public:
Path() { path = new vector; }
~Path() { delete path; }
Path* duplicate() const {
Path *np = new Path;
np->path = new vector(*path);
return np;
}
vector *path;
};
class Solution {
public:
vector> findLadders(string start, string end, unordered_
set &dict) {
vector> ans;
queue q;
Path *np = new Path;
np->path->push_back(&start);
q.push(np);
unordered_set used;
queue levelUsed;
while (!q.empty()) {
int n = q.size();
while (n-- > 0) {
Path *p = q.front();
string temp(*p->path->back());
for (int i = 0; i < temp.size(); i++) {
char tc = temp[i];
for (int j = 0; j < 26; j++) {
if (tc == (char)('a' + j))
continue;
temp[i] = (char)('a' + j);
unordered_set::iterator it = dict.find(temp);
if (it != dict.end() && used.find(&(*it)) == used.
end()) {
np = p->duplicate();
np->path->push_back(&(*it));
if (temp == end) {
vector line;
for (vector::iterator itv =
np->path->begin(); itv != np->path->end(); itv++)
line.push_back(**itv);
ans.push_back(line);
}
q.push(np);
levelUsed.push(&(*it));
}
}
temp[i] = tc;
}
q.pop();
delete p;
}
if (!ans.empty())
break;
while(!levelUsed.empty()) {
used.insert(levelUsed.front());
levelUsed.pop();
}
}
return ans;
}
};
class Path {
public:
Path() { path = new vector
~Path() { delete path; }
Path* duplicate() const {
Path *np = new Path;
np->path = new vector
return np;
}
vector
};
class Solution {
public:
vector
set
vector
queue
Path *np = new Path;
np->path->push_back(&start);
q.push(np);
unordered_set
queue
while (!q.empty()) {
int n = q.size();
while (n-- > 0) {
Path *p = q.front();
string temp(*p->path->back());
for (int i = 0; i < temp.size(); i++) {
char tc = temp[i];
for (int j = 0; j < 26; j++) {
if (tc == (char)('a' + j))
continue;
temp[i] = (char)('a' + j);
unordered_set
if (it != dict.end() && used.find(&(*it)) == used.
end()) {
np = p->duplicate();
np->path->push_back(&(*it));
if (temp == end) {
vector
for (vector
np->path->begin(); itv != np->path->end(); itv++)
line.push_back(**itv);
ans.push_back(line);
}
q.push(np);
levelUsed.push(&(*it));
}
}
temp[i] = tc;
}
q.pop();
delete p;
}
if (!ans.empty())
break;
while(!levelUsed.empty()) {
used.insert(levelUsed.front());
levelUsed.pop();
}
}
return ans;
}
};
i*e
122 楼
我测试了你的程序,差不多4秒跑完所有test。
简单优化了一下变成3.5秒,还差1.5秒。
说说你duplicate 路径的时候怎么做的?
有把之前共享的路径也copy 下来了吗?
【在 f*******t 的大作中提到】
: 相当丑陋的BFS,已经尽量去除copy string的时间了,但还是超时,求指点T_T
: class Path {
: public:
: Path() { path = new vector; }
:
: ~Path() { delete path; }
:
: Path* duplicate() const {
: Path *np = new Path;
: np->path = new vector(*path);
简单优化了一下变成3.5秒,还差1.5秒。
说说你duplicate 路径的时候怎么做的?
有把之前共享的路径也copy 下来了吗?
【在 f*******t 的大作中提到】
: 相当丑陋的BFS,已经尽量去除copy string的时间了,但还是超时,求指点T_T
: class Path {
: public:
: Path() { path = new vector
:
: ~Path() { delete path; }
:
: Path* duplicate() const {
: Path *np = new Path;
: np->path = new vector
y*e
124 楼
DFS+pruning?
那步dict.erase()用的很妙
展开说说怎么想到的吧~
vector<
【在 t********6 的大作中提到】
: 第二题,求指导:
: class Solution {
: public:
: void traverse(string& start, string& root, unordered_map : string> >& prev, vector& current, vector>& result) {
: auto iter = prev.find(root);
: for (string str : iter->second) {
: current.push_back(str);
: if (str == start) {
: vector new_one(current.size());
那步dict.erase()用的很妙
展开说说怎么想到的吧~
vector<
【在 t********6 的大作中提到】
: 第二题,求指导:
: class Solution {
: public:
: void traverse(string& start, string& root, unordered_map
: auto iter = prev.find(root);
: for (string str : iter->second) {
: current.push_back(str);
: if (str == start) {
: vector
l*0
127 楼
学习了!
c*a
128 楼
word ladder I的话只要BFS就够了(java),想要大set不超时,关键就是一边加新词
进queue,一边从dict里remove掉。
进queue,一边从dict里remove掉。
l*1
129 楼
这个题用DFS怎么做? 是IDDFS?
我用BFS,JAVA写的代码I能过,II的大数据过不了,代码和上面有人贴的很像,不知道
有什么要注意的?
我用BFS,JAVA写的代码I能过,II的大数据过不了,代码和上面有人贴的很像,不知道
有什么要注意的?
相关阅读