This accepted solution should be wrong, lack of test cases maybe?


  • 0
    K
    class Solution {
    public:
        
        int ladderLength(string start, string end, unordered_set<string> &dict) {
            queue<string> que;
            unordered_set<string> visited;
            int depth = 1;
            const string label_of_depth = "#";
            que.push(start);
            que.push(label_of_depth);
            typedef unordered_set<string>::iterator IT;
            while(!que.empty()) {
                string tmp = que.front();
                que.pop();
                if(tmp == label_of_depth) {
                    ++depth;
                    if(!que.empty()) que.push(label_of_depth);
                    continue;
                }
                for(int i = 0; i < tmp.size(); ++i) {
                    string changed = tmp;
                    for(char c ='a'; c <= 'z'; ++c) {
                        changed[i] = c;
                        if(dict.count(changed) > 0 && visited.count(changed) == 0) {
                            que.push(changed);
                            visited.insert(changed);
                            if(changed == end) return depth+1;
                        }
                    }
                }
            }
            return 0;
        }
    };
    

    This solution passed the OJ, but when end is not in dict, it should return 0, which could be wrong,
    right?


  • 0

    Could you please give an example test case and its expected output?


  • 0
    K

    any test case when end is not included in the dict. I test the case given in the problem description locally, and the return value is 0. I wandered how it could pass the oj.


  • 0
    C

    dict doesn't contain start or end, it only contains intermediate words


  • 0
    K

    on one hand I think dict can contain start or end, if it can't, more reasons that this solution should be rejected?


Log in to reply
 

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