Why can't I pass the case "hot","dog" {"hot","dog","dot"}?


  • 0
    1

    class Node{
    private:
    public:
    int level;
    string word;
    Node(int x,string word){
    level=x;
    this->word=word;
    }

    };
    class Solution {
    public:

    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
        queue<Node> q;
        unordered_set<string> del;
        Node begin(1,beginWord);
        q.push(begin);
        del.insert(beginWord);
        int ret=0;
        if(beginWord==endWord) return 1;
        while(!q.empty()){
            string tword=q.front().word;
            int tlevel=q.front().level;
            Node now(tlevel,tword);
            q.pop();
            string s=now.word;
            if(s==endWord) {
                ret=now.level;
                break;
            }
            for(int i=0;i<s.length();i++){
                for(int j=0;j<26;j++){
                    s[i]='a'+j;
                    if(wordDict.find(s)!=wordDict.end()&&del.find(s)==del.end()&&s!=now.word){
                        Node tmp(now.level+1,s);
                        q.push(tmp);
                        del.insert(s);
                    }
                }
            }
        }
        return ret;
        
    }
    

    };

    The answer should be 3 while my code returns 0.


  • 1
    B

    I think it's because you forget to convert the string "s" to its origin character.
    Please look at the comment below.

    for(int i=0;i<s.length();i++){
                for(int j=0;j<26;j++){
                    s[i]='a'+j;    //here you changed the character of the string s
                    if(wordDict.find(s)!=wordDict.end()&&del.find(s)==del.end()&&s!=now.word){
                        Node tmp(now.level+1,s);
                        q.push(tmp);
                        del.insert(s);
                    }
                }
            }

Log in to reply
 

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