Standard DFS but TLE, why???


  • 0
    D

    The idea is pretty the same as other AC codes, and I also erase word from the wordList, but still TLE. Any improvement can be done?

    class Solution {public:
    int diff(string word1,string word2)
    {
        
        int i,res=0;
        for(i=0;i<word1.size();i++)
            if(word1[i]!=word2[i])
                res++;
        return res;
    }
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        deque<string> queue;
        map<string,int> depth;
        queue.push_front(beginWord);
        depth[beginWord]=1;
        while(!queue.empty())
        {
            if(queue[0]==endWord)
                return depth[endWord];
            for(auto it=wordList.begin();it!=wordList.end();)
            {
                if(diff(*it,queue[0])==1)
                {
                    queue.push_back(*it);
                    depth[*it]=depth[queue[0]]+1;
                    it=wordList.erase(it);
                }
                else 
                    it++;
                
            }
            queue.pop_front();
        }
        return 0;
    }};

Log in to reply
 

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