Test case failed here but passed in my Visual Studio


  • 0
    C

    The idea: After boundary check, we put the start & end into a set (found), erase the start & end from the dictionary. Then scan the dictionary to find the one letter different word. Update the searching word & keep going.

    In this test case: //"teach", "place"
    //["peale","wilts","place","fetch","purer","pooch","peace","poach","berra","teach","rheum","peach"]
    I got 4 in Visual Studio but got 0 in leetcode. Any one help?

    class Solution {
    public:
        int ladderLength(string start, string end, unordered_set<string> &dict) {
            
            if(start.size()==0 ||start==end) return 0;
            if(start.size()==1) return 2;
            if(diffCnt(start,end)==1) return 2;
            
            curr=start;
            last=end;
    
            found.insert(start); found.insert(last);
            dict.erase(start); dict.erase(last);
            
            while(1)
            {
                int ret=scanDict(curr,dict);
                if(ret==0)
                {
                    return found.size();
                }
                else if(ret==2)
                {
                    break;
                }
            }
            
            return 0;
        }
        
        int scanDict(string s, unordered_set<string> &dict)
        {
            unordered_set<string>::iterator it = dict.begin(); //never worry about iterator after reset
            
            while(it!=dict.end())
            {
                string tmp=*it;
                int diffs=diffCnt(s,tmp);
                if(diffs==1)
                {
                    found.insert(tmp);
                    dict.erase(it);
                    curr=tmp;
                    
                    if(diffCnt(tmp,last)==1)
                    {
                        // found the last one for completion
                        return 0;
                    }
                    return 1;  // caller needs to keep searching
                }
                
                it++;
            }
            return 2;  //nothing with one letter difference word
        }
        
        int diffCnt(string &s1, string &s2)
        {
            int cnt=0;
            for(int i=0;i<s1.size();i++)
            {
                if(s1[i]!=s2[i]) cnt++;
            }
            return cnt;
        }
        
        string curr,last;
        
        set<string> found;
    };

  • 0
    G

    I confronted the same question in C# but in another test case (please refer to my last post).

    My code runs fine in Visual Studio (output 2) but failed in OJ (output 0).

    Question asked and still waiting for answer.

    If you have the idea, please share with me.

    Thanks


Log in to reply
 

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