Please tell me why I didn't pass the testcase


  • 1
    L

    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;
        }
    };
    

  • 1
    L

    @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?


  • 0
    G

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


  • 0
    L

    @Gary2954 Thanks~


Log in to reply
 

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