127. Word Ladder

思路：

双边dfs

双边bfs

class Solution {

private:

    typedef vector<vector<int>> graph;

    bool hasPath(string& w1, string& w2){

        int len = w1.length();

        int diff = 0;

        for(int i = 0; i < len; i++){

            if(w1[i] != w2[i])

                diff++;

            if(diff > 1)

                return false;

        }

        return true;

    }

    graph buildGraph(vector<string>& wordList){

        graph G = graph(wordList.size());

        for(int i = 0; i < wordList.size(); i++)

            for(int j = i + 1; j < wordList.size(); j++){

                if(hasPath(wordList[i], wordList[j])){

                    G[i].push_back(j);

                    G[j].push_back(i);

                }

            }

        return G;

    }

public:

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

        int n = wordList.size();

        auto it = wordList.begin();

        int end = find(it, it + n, endWord) - it;



        if(end == n) return 0;

        int start = find(it, it + n, beginWord) - it;

        if(start == n){

            wordList.push_back(beginWord);

            n++;

        }



        graph G = buildGraph(wordList);



        vector<int> visited_s(n, 0);

        vector<int> visited_t(n, 0);



        vector<int> step_s(n, 0);

        vector<int> step_t(n, 0);



        queue<int> qs;

        queue<int> qt;



        qs.push(start); qt.push(end);

        step_s[start] = 1; step_t[end] = 1;

        int res = n + 1;

        while(!qs.empty() && !qt.empty()){

            // bfs from begin

            int s = qs.front(); qs.pop();

            for(auto& w : G[s]){

                if(step_s[w] == 0){

                    qs.push(w);

                    step_s[w] = step_s[s] + 1;

                }

            }



            // bfs from end

            int t = qt.front(); qt.pop();

            for(auto& w : G[t]){

                if(step_t[w] == 0){

                    qt.push(w);

                    step_t[w] = step_t[t] + 1;

                }

            }



            // check for intersection

            int res = n + 1; // initialize possible distance

            for(int i = 0; i < n; i++){

                if(step_s[i] > 0 && step_t[i] > 0)

                    res = min(res, step_s[i] + step_t[i] - 1);

            }

            if(res < n + 1)

                return res;

        }

        return 0;

    }

};

class Solution {

public:

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

        int end = find(wordList.begin(), wordList.end(), endWord)-wordList.begin();

        if (end == wordList.size())

            return 0;

        int begin = find(wordList.begin(), wordList.end(), beginWord)-wordList.begin();

        if (begin == wordList.size())

            wordList.push_back(beginWord);



        int n = wordList.size();



        vector<vector<int>> graph(n, vector<int>());

        for(int i=0;i<n;i++)

            for(int j=0;j<i;j++)

                if (hasPath(wordList[i],wordList[j])){

                    graph[i].push_back(j);

                    graph[j].push_back(i);

                }



        // BFS

        queue<int> q_s;

        queue<int> q_t;



        vector<int> step_s(n,0);

        vector<int> step_t(n,0);



        q_s.push(begin); q_t.push(end);

        step_s[begin]=1; step_t[end]=1;



        while(!q_s.empty() && !q_t.empty()) {

            int cur_s = q_s.front();

            q_s.pop();



            // for(int i=0;i<n;i++) {

            //     // step_s[i]表示begin到第i个单词的距离

            //     // 只更新还未访问过的点，step为0代表还未访问过

            //     if (step_s[i] == 0 && graph[cur_s][i]){

            //         step_s[i] = step_s[cur_s]+1;

            //         q_s.push(i);

            //     }

            // }

            for(int i:graph[cur_s])

                if(step_s[i] == 0) {

                    step_s[i] = step_s[cur_s]+1;

                    q_s.push(i);

                }



            int cur_t = q_t.front();

            q_t.pop();

            for(int j: graph[cur_t])

                if(step_t[j] == 0) {

                    step_t[j] = step_t[cur_t]+1;

                    q_t.push(j);

                }

            // for(int i=0;i<n;i++) {

            //     if(step_t[i] == 0 && graph[cur_t][i]) {

            //         step_t[i] = step_t[cur_t] + 1;

            //         q_t.push(i);

            //     }

            // }



            // 检查st是否相交

            int res = n + 1;

            for(int i=0;i<n;i++)

                //i能被st同时到达

                if(step_s[i]!=0 && step_t[i]!=0)

                    res=min(step_s[i]+step_t[i]-1,res);

            if(res<n+1)

                return res;

        }

        return 0;

    }



    bool hasPath(const string& i, const string& j) {

        if(i == "" || i.size() != j.size() || i==j)

            return false;

        int diff = 0;

        for(int k=0;k<i.size();k++){

            if(i[k] != j[k])

                diff++;

            if (diff > 1)

                return false;

        }

        return true;

    }

};