EITO# Joke - 肚皮舞运动
A*g
1 楼
Leetcode OJ里的word ladder, 过了小test，大test第一个就超时了，不解！
用的是BFS算法，请大牛们看看有什么问题，谢谢！
class Solution {
public:
typedef unordered_map > Graph;
bool has_edge(string a, string b) {
if (a.size() != b.size()) {
return false;
}
int diff = 0;
for (int i=0; i
diff++;
}
return diff==1;
}
void build_graph(string &start, string &end, unordered_set &dict
, Graph &G) {
unordered_set neighbors;
G[start+"s"] = neighbors;
G[end+"e"] = neighbors;
for (auto itr=dict.begin(); itr!=dict.end(); ++itr) {
G[*itr+"m"] = neighbors;
}
for (auto itr=G.begin(); itr!=G.end(); ++itr) {
for (auto itr2=G.begin(); itr2!=G.end(); ++itr2) {
if( has_edge( itr->first.substr(0,itr->first.size()-1),
itr2->first.substr(0,itr2->first.size()-1)) )
itr->second.insert(itr2->first);
}
}
}
void init_distance( unordered_map &distance, Graph &G) {
for (auto itr=G.begin(); itr!=G.end(); ++itr) {
distance[itr->first] = INT_MAX;
}
}
void BFS(string start, string end, Graph &G, unordered_map &
distance) {
queue q;
q.push(start);
distance[start] = 0;
while(q.size() != 0) {
string s = q.front();
q.pop();
for (auto itr=G[s].begin(); itr!=G[s].end(); ++itr) {
if (distance[*itr] == INT_MAX) {
distance[*itr] = distance[s]+1;
q.push(*itr);
}
}
}
}
int ladderLength(string start, string end, unordered_set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
Graph G;
build_graph(start, end, dict, G);
unordered_map distance;
init_distance( distance, G);
BFS(start+"s", end+"e", G, distance);
if (distance[end+"e"] == INT_MAX) //can't reach, word ladder has
length 0
return 0;
int ret = distance[end+"e"]+1;
return ret;
}
};
用的是BFS算法，请大牛们看看有什么问题，谢谢！
class Solution {
public:
typedef unordered_map
bool has_edge(string a, string b) {
if (a.size() != b.size()) {
return false;
}
int diff = 0;
for (int i=0; i
diff++;
}
return diff==1;
}
void build_graph(string &start, string &end, unordered_set
, Graph &G) {
unordered_set
G[start+"s"] = neighbors;
G[end+"e"] = neighbors;
for (auto itr=dict.begin(); itr!=dict.end(); ++itr) {
G[*itr+"m"] = neighbors;
}
for (auto itr=G.begin(); itr!=G.end(); ++itr) {
for (auto itr2=G.begin(); itr2!=G.end(); ++itr2) {
if( has_edge( itr->first.substr(0,itr->first.size()-1),
itr2->first.substr(0,itr2->first.size()-1)) )
itr->second.insert(itr2->first);
}
}
}
void init_distance( unordered_map
for (auto itr=G.begin(); itr!=G.end(); ++itr) {
distance[itr->first] = INT_MAX;
}
}
void BFS(string start, string end, Graph &G, unordered_map
distance) {
queue
q.push(start);
distance[start] = 0;
while(q.size() != 0) {
string s = q.front();
q.pop();
for (auto itr=G[s].begin(); itr!=G[s].end(); ++itr) {
if (distance[*itr] == INT_MAX) {
distance[*itr] = distance[s]+1;
q.push(*itr);
}
}
}
}
int ladderLength(string start, string end, unordered_set
// Start typing your C/C++ solution below
// DO NOT write int main() function
Graph G;
build_graph(start, end, dict, G);
unordered_map
init_distance( distance, G);
BFS(start+"s", end+"e", G, distance);
if (distance[end+"e"] == INT_MAX) //can't reach, word ladder has
length 0
return 0;
int ret = distance[end+"e"]+1;
return ret;
}
};
