# Please tell me why I didn't pass the testcase

• Hi, I solved this problem using dijsktra algorithm. But I passed 38 / 39 cases. The lase cases I didn't pass is :

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

My code is as follows :

``````class Solution {
private:
vector<string> words;
struct pathRecord{
int dist;
bool visited;
pathRecord(int dist = -1) : dist(dist), visited(false) {}
};

bool hasPath(string &w1, string &w2) {
if (w1.size() != w2.size()) {
return false;
}
bool hasP = false;
for (int i = 0;i < w1.size();i++) {
if (w1[i] != w2[i]) {
if (hasP) {
return false;
}
hasP = true;
}
}
return hasP;
}

public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if (wordList.size() == 0) {
return 0;
}
words.push_back(beginWord);
words.push_back(endWord);
for(int i = 0;i < wordList.size();i++) {
words.push_back(wordList[i]);
}
//construct the graph
unordered_map<int, vector<int> > maps;
for (int i = 0;i < words.size();i++) {
for (int j = i + 1; j < words.size();j++) {
if (hasPath(words[i], words[j])) {
maps[i].push_back(j);
maps[j].push_back(i);
}
}
}
//dijkstra
pathRecord tmp = pathRecord(-1);
vector<pathRecord> paths(words.size(), tmp);
paths[0].dist = 0;
for (int i = 0;i < words.size();i++) {
int minDist = INT_MAX;
int minNode = -1;
for (int j = 0;j < words.size();j++) {
if (!paths[j].visited && paths[j].dist != -1 && minDist > paths[j].dist) {
minDist = paths[j].dist;
minNode = j;
}
}
if (minNode == -1) {
break;
}
paths[minNode].visited = true;
for (int j = 0; j < maps[minNode].size();j++) {
int index = maps[minNode][j];
if (paths[index].dist == -1 || paths[index].dist > minDist) {
paths[index].dist = paths[minNode].dist + 1;
}
}
if (paths[1].visited) {
break;
}
}
return paths[1].dist + 1;
}
};
``````

• @LionZhou I'm sorry that I didn't make it clear. The answer I output is 5, but the right answer was supposed to be 0, which I don't know why. So please anyone tell me? Or the test case is wrong?

• The endWord is not in the worList. Therefore, the result is 0.

• @Gary2954 Thanks~

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.