Is BFS sufficient for Word Ladder?


  • 0
    V
    class Solution {
    public:
    queue<pair<string,int> > q;
    string finalend;
    map<string,bool> visited;
    
    int combinations(string s,int count, unordered_set<string> &dict){
        int n=s.size();
        string temp;
        for(int i=0;i<n;i++){
            temp=s;
            for(char j='a'; j<='z';j++){
                temp[i]=j;
                if(temp==finalend)return count;
                if(dict.find(temp)!=dict.end()&&visited[temp]==false){
                    visited[temp]=true; // code edited here. This gave me Accepted.
                    q.push(make_pair(temp,count));
                }
            }
        }
        return -1;
    }
    
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        if(start==end)return 0;
        int count=1;
        finalend=end;
        q.push(make_pair(start,count));
        while(!(q.empty())){
            pair<string,int> t=q.front();
            q.pop();
            visited[t.first]=true;
            int result=combinations((t.first),((t.second)+1),dict);
            if(result!=-1){
                return result; 
            }
        }
        return 0;
    }
    };
    

    Got Accepted after setting visited to true for each neighbor added to queue.

    I am using the pair of the STL in C++. I am getting TLE. Is BFS sufficient for this problem or do we need any other approach like double BFS ?
    Thank you.


Log in to reply
 

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