Time limit exceeded for Word Ladder(leetcode)# JobHunting - 待字闺中
x*0
1 楼
按照leetcode的建议，用先变再查的方法来判断相邻的word。对大数据还是超时了。
下面是我的code，大家可不可以帮忙看看。
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
unordered_set visited;
queue q;
q.push(start);
int curLevelLen = 1;
int nextLevelLen = 0;
int level = 1;
while (dict.size() > 0 && !q.empty()) {
string cur(q.front());
q.pop();
visited.insert(cur);
for (int i = 0; i < cur.size(); ++i) {
for (int j = 'a'; j <= 'z'; ++j) {
char copy = cur[i];
if (j == cur[i]) {
continue;
}
cur[i] = j;
if (cur == end) {
return level+1;
}
if (dict.find(cur) != dict.end() &&
visited.find(cur) == visited.end()) {
//if (dict.count(cur) > 0 && visited.count(cur) == 0)
q.push(cur);
++nextLevelLen;
}
cur[i] = copy;
}
}
--curLevelLen;
if (curLevelLen == 0) {
++level;
curLevelLen = nextLevelLen;
nextLevelLen = 0;
}
}
return 0;
}
};
下面是我的code，大家可不可以帮忙看看。
class Solution {
public:
int ladderLength(string start, string end, unordered_set
// Start typing your C/C++ solution below
// DO NOT write int main() function
unordered_set
queue
q.push(start);
int curLevelLen = 1;
int nextLevelLen = 0;
int level = 1;
while (dict.size() > 0 && !q.empty()) {
string cur(q.front());
q.pop();
visited.insert(cur);
for (int i = 0; i < cur.size(); ++i) {
for (int j = 'a'; j <= 'z'; ++j) {
char copy = cur[i];
if (j == cur[i]) {
continue;
}
cur[i] = j;
if (cur == end) {
return level+1;
}
if (dict.find(cur) != dict.end() &&
visited.find(cur) == visited.end()) {
//if (dict.count(cur) > 0 && visited.count(cur) == 0)
q.push(cur);
++nextLevelLen;
}
cur[i] = copy;
}
}
--curLevelLen;
if (curLevelLen == 0) {
++level;
curLevelLen = nextLevelLen;
nextLevelLen = 0;
}
}
return 0;
}
};