The BFS approach is better than DFS that times out!


  • 0
    L

    This is why we need BFS since DFS approach times out as per OJ test.

    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList)
    {
        int ret;
        ret = ladderLength(beginWord, endWord, wordList,0);
        
        if( ret== INT_MAX)
            return 0;
        return ret;
    }
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList, int pos)
    {
        queue<string> q;
        
        q.push(beginWord);
        int dist=1;
        
        while(!q.empty())
        {
            int num=q.size();
            for(int i =0;i<num;i++)
            {
                string cur = q.front();
                q.pop();
                
                if(cur == endWord)
                    return dist;
                
                for(int pos=0; pos<beginWord.length(); pos++)
                for(char c='a' ; c <='z'; c++)
                {
                    char orig= cur[pos];
                    cur[pos]=c;
                    
                    auto it = wordList.find(cur);
                    if( it != wordList.end() )
                    {
                        q.push(cur);
                        wordList.erase(it);
                    }
                    cur[pos] = orig;
                }
            }
            dist++;
        }
        return 0;
        
    }
    // this one times out. 
    int ladderLengthdfs(string beginWord, string endWord, unordered_set<string>& wordList, int pos)
    {
        if( beginWord == endWord)
            return 0;
        else
        {
            int mint= INT_MAX;
            string temp = beginWord;
            for(int pos=0;pos<beginWord.length();pos++)
            for(char c='a' ; c <='z'; c++)
            {
                char orig=  temp[pos];
                temp[pos] =c ;
                
                auto it = wordList.find(temp);
                if( it!= wordList.end() )
                {
                    wordList.erase(it);
                    int ret=ladderLengthdfs(temp, endWord, wordList,pos);
                    wordList.insert(temp);
                    if(ret != INT_MAX)
                        ret+=1;
                    
                    mint = min(mint, ret);
                }
                temp[pos] = orig ;
            }
            
            return mint;
        }
    }

Log in to reply
 

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