Simple BFS solution


  • 0
    J
    using namespace std;
    
    #define PI acos(-1)
    #define sqr(x) ((x) * (x))
    #define PB push_back
    #define MP make_pair
    #define F first
    #define S second
    #define ALL(c) (c).begin(), (c).end()
    #define SIZE(c) (int)(c).size()
    #define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
    #define REPD(i, a, b) for (int i = int(a); i >= int(b); i--) 
    
    typedef unsigned long long ull;
    typedef long long ll;
    typedef pair<int,int> ii;
    typedef pair<double,double> dd;
    typedef vector<int> vi;
    typedef vector<vi> vvi;
    typedef vector<ii> vii;
    typedef vector<vii> vvii;
    typedef vector<string> vs;
    typedef map<int,int> mii;
    typedef map<string, int> msi;
    typedef set<int> si;
    
    const int INF=1 << 28;
    
    class Solution {
    public:
        int ladderLength(string start, string end, unordered_set<string> &dict) {
            int n = SIZE(dict) + 2, v = 0, wl = start.length(), dist[n];
            bool disc[n];
            msi h;
            REP(i, 0, n-1) { dist[i]=INF; disc[i]=false; }
            queue<string> q;
            
            h[start]=v++;
            for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it) { 
                if(*it != start) { 
                    h[*it]=v++; 
                }
            }
            h[end]=v;
            
            q.push(start);
            dist[h[start]]=1; //path length is vertex count along path, not edges
            disc[h[start]]=true;
            string u;
            char buf[wl+1];
    
            while(!q.empty()) {
                u=q.front(); q.pop();
    
                REP(i, 0, wl-1) {
                    REP(j, 0, 25) {
                        strcpy(buf, u.c_str());
                        buf[i]='a'+j;
                        string y(buf);
                        
                        if(h.find(y) != h.end() && y != start) {
                            int x=h[y];
                            if(!disc[x]) {
                                if(y == end) {
                                    dist[x] = min(dist[x], dist[h[u]]+1);
                                }else {
                                    q.push(y);
                                    disc[x]=true;
                                    dist[x]=dist[h[u]]+1;
                                }
                            }
                        }
                    }
                }
            }
            
            if(dist[h[end]] == INF) { return 0; }
            else { return dist[h[end]]; }
        }
    };

Log in to reply
 

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