C++ Self comment dj shortest path solution.


  • 0
    F
    class Solution {
        bool can_linked(string str_1, string str_2) {
            if (str_1 == str_2) {return false;}
            assert(str_1.size() == str_2.size() && !str_1.empty());
            int pos = 0;
            int check = 0;
            for (; check < 2 && pos < str_1.size(); pos++) {
                if (str_1[pos] == str_2[pos]) {
                    
                } else {
                    check++;
                }
            }
            if (check == 1) {
                return true;
            } else {
                return false;
            }
        }
        struct x_node {
            string val_;
            int deepth_ = numeric_limits<int>::max();
            vector<x_node*> neighbors_;
            x_node(string v) : val_(v) {}
        };
        unordered_map<string, x_node*> map_;
        set<x_node*> unvisited_;
        set<x_node*> visited_;
        int djs_from_to(x_node* b, x_node* e) {
            unvisited_.emplace(b);
            assert(b != nullptr);
            b->deepth_ = 1;
            while (!unvisited_.empty()) {
                // pick smallest deepth in unvisited
                x_node* to_visit;
                int smallest_deepth = numeric_limits<int>::max();
                auto found = for_each(unvisited_.begin(), unvisited_.end(), [&to_visit, &smallest_deepth](x_node* xn) {
                    if (xn->deepth_ < smallest_deepth) {
                        smallest_deepth = xn->deepth_;
                        to_visit = xn;
                    }
                });
                // visit it and update deepth of its neighbor
                visited_.emplace(to_visit);
                if (to_visit == e) {
                    return to_visit->deepth_;
                }
                unvisited_.erase(unvisited_.find(to_visit));
                for (auto nei : to_visit->neighbors_) {
                    auto found_1 = visited_.find(nei);
                    if (found_1 != visited_.end()) {
                        
                    } else {
                        unvisited_.emplace(nei);
                        if (nei->deepth_ > to_visit->deepth_ + 1) {
                            nei->deepth_ = to_visit->deepth_ + 1;
                        }
                    }
                }
            }
            return 0;
        }
        
    public:
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
            // build graph
            for (auto s : wordList) {
                x_node* nd = new x_node(s);
                map_[s] = nd;
            }
            x_node* nd = new x_node(beginWord);
            map_[beginWord] = nd;
            // build neighbor of graph nodes
            for (int i = 0; i < wordList.size(); i++) {
                string s = wordList[i];
                for (int j = i; j < wordList.size(); j++) {         // O(n2)
                    string ls = wordList[j];
                    if (can_linked(s, ls)) {
                        map_[s]->neighbors_.push_back(map_[ls]);
                        map_[ls]->neighbors_.push_back(map_[s]);
                    }
                }
            }
            for (int j = 0; j < wordList.size(); j++) {        
                string ls = wordList[j];
                if (can_linked(beginWord, ls)) {
                    map_[beginWord]->neighbors_.push_back(map_[ls]);
                    map_[ls]->neighbors_.push_back(map_[beginWord]);
                }
            }
            // dj shortest path from beginword to endword
            return djs_from_to(map_[beginWord], map_[endWord]);
        }
    };
    

Log in to reply
 

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