[word ladder][TLE] recent problem ont word ladder


  • 0
    S

    Hi,
    I am using hash+deque to solve the problem.
    But my code got TLE when dealing with big dict.

    Can anyone give me some advise?

    THanks

    class Solution {
    private:
        bool isNabor(string a, string b){   // assume that a and b has the same length.
            int i, dif;
            dif = 0;
            for (i=0; i<a.size(); ++i){
                if(a[i]!=b[i]){
                    ++dif;
                }
                if (dif>1)
                {
                    return false;
                }
            }
            return true;
        }
    public:
        int ladderLength(string start, string end, unordered_set<string> &dict) {
            // use a deque to implement the BFS...
            // use a hash table(unordered_map) to keep the visiting information.
            deque<string> que;
            unordered_map<string, int> dist;
            string cur;
            
        que.clear();
        dist.clear();
        
        que.push_back(start);
        dist[start] = 1;        // Not 0!!
        
        while(!que.empty()){
            cur = que.front();  // get current string;
            que.pop_front();    // and clean it from the queue
            
            // check though all words in the dictionary
            for ( unsigned i = 0; i < dict.bucket_count(); ++i) {
                for ( auto local_it = dict.begin(i); local_it!= dict.end(i); ++local_it ){
                    // if this word is not visited and is nabor with cur string, then update in in queue
                    if((0==dist.count(*local_it))&&isNabor(cur, *local_it)){
                        dist[*local_it] = dist[cur]+1;
                        que.push_back(*local_it);
                        // dist.erase(*local_it); // pruning
                    }
                    if((end==*local_it)&&dist.count(end))   //dist.count(end) is important!
                        return dist[end];
                }
                    
            }
        
        }
        
        return 0;   //impossible..
    }
    

    };


  • 0
    S
    bool isNabor(string a, string b)
    

    is taking a lot of time...so, better to use other ways to do this task.


  • 0
    S

    bool isNabor(string a, string b)

    is taking a lot of time...so, better to use other ways to do this task.


Log in to reply
 

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