720ms solution in C++


  • 2
    W

    class Solution {
    public:

    void calAdj(const string s, unordered_set<string> & dict, unordered_set<string>& adjset){
         adjset.clear();
         for( int i = 0; i < s.size(); ++i){
             string tmp(s);
             for( char az = 'a'; az <= 'z'; ++az){
                 tmp[i] = az;
                 if( dict.find(tmp) != dict.end()){ //tmp is in dictionary
                     adjset.insert(tmp);
                 }
             }
         }
    }
    
    void pathreverse(unordered_map<string, unordered_set<string>>& pathmap, string start, vector<vector<string>>& pathlist){
         
         vector<string> & lastpath = pathlist[pathlist.size()-1];
         lastpath.push_back( start );
         vector<string> prepath(lastpath);
         
         int p = 0;
         for( auto nstr : pathmap[start] ){
              if( p > 0 )//generate new path
                  pathlist.push_back(prepath);
              pathreverse(pathmap, nstr, pathlist);
              ++p;
         }
    }
    
    vector< vector<string> > findLadders(string start, string end, unordered_set<string> &dict){
          
          vector< vector<string> > pathlist;
          string tmp = start;
          start = end;
          end = tmp;
          int slen = start.size();
          int elen = end.size();
          if( slen != elen )
              return pathlist;
          
          dict.insert(start);
          dict.insert(end);
          
          //run bfs
          unordered_map<string, unordered_set<string>> pathmap;
          unordered_set<string> curset;
          curset.insert(start);
          dict.erase(start);
          unordered_set<string> adjset;
          bool find = false;
          
          while( !find && curset.size() > 0 ){
               unordered_set<string> preset(curset);
               curset.clear();
               for( auto pres : preset){
                    if( pres == end ){//find it
                        find = true;
                        pathlist.push_back(vector<string>());
                        pathreverse(pathmap, end, pathlist);
                        break;
                    }
                    calAdj(pres, dict, adjset);
                    curset.insert(adjset.begin(),adjset.end());//put in next layer
                    for( auto nexts : adjset ){
                         pathmap[nexts].insert(pres); // record its parents
                    }
               }
               for( auto vs : curset) // remove visited string
                    dict.erase(vs);
          }
          return pathlist;
    }
    

    };


  • 0
    U

    helpful~~ great!


  • 0
    C

    why the value of pathmap is set? seems vector is enough.

    learn a technique~

    for (auto it : container)


  • 0

    In fact, for this problem, use two-end BFS is a better idea, here is my 88ms c++ solution:

    class Solution {
    public:
        std::vector<std::vector<std::string> > findLadders(std::string beginWord, std::string endWord, std::unordered_set<std::string> &dict) {
            std::vector<std::vector<std::string> > paths;
            std::vector<std::string> path(1, beginWord);
            if (beginWord == endWord) {
                paths.push_back(path);
                return paths;
            }
            std::unordered_set<std::string> words1, words2;
            words1.insert(beginWord);
            words2.insert(endWord);
            std::unordered_map<std::string, std::vector<std::string> > nexts;
            bool words1IsBegin = false;
            if (findLaddersHelper(words1, words2, dict, nexts, words1IsBegin))
                getPath(beginWord, endWord, nexts, path, paths);
            return paths;
        }
    private:
        bool findLaddersHelper(
            std::unordered_set<std::string> &words1,
            std::unordered_set<std::string> &words2,
            std::unordered_set<std::string> &dict,
            std::unordered_map<std::string, std::vector<std::string> > &nexts,
            bool &words1IsBegin) {
            words1IsBegin = !words1IsBegin;
            if (words1.empty())
                return false;
            if (words1.size() > words2.size())
                return findLaddersHelper(words2, words1, dict, nexts, words1IsBegin);
            for (auto it = words1.begin(); it != words1.end(); ++it)
                dict.erase(*it);
            for (auto it = words2.begin(); it != words2.end(); ++it)
                dict.erase(*it);
            std::unordered_set<std::string> words3;
            bool reach = false;
            for (auto it = words1.begin(); it != words1.end(); ++it) {
                std::string word = *it;
                for (auto ch = word.begin(); ch != word.end(); ++ch) {
                    char tmp = *ch;
                    for (*ch = 'a'; *ch <= 'z'; ++(*ch))
                        if (*ch != tmp)
                            if (words2.find(word) != words2.end()) {
                                reach = true;
                                words1IsBegin ? nexts[*it].push_back(word) : nexts[word].push_back(*it);
                            }
                            else if (!reach && dict.find(word) != dict.end()) {
                                words3.insert(word);
                                words1IsBegin ? nexts[*it].push_back(word) : nexts[word].push_back(*it);
                            }
                    *ch = tmp;
                }
            }
            return reach ? true : findLaddersHelper(words2, words3, dict, nexts, words1IsBegin);
        }
    private:
        void getPath(
            std::string beginWord,
            std::string &endWord,
            std::unordered_map<std::string, std::vector<std::string> > &nexts,
            std::vector<std::string> &path,
            std::vector<std::vector<std::string> > &paths) {
            if (beginWord == endWord)
                paths.push_back(path);
            else
                for (auto it = nexts[beginWord].begin(); it != nexts[beginWord].end(); ++it) {
                    path.push_back(*it);
                    getPath(*it, endWord, nexts, path, paths);
                    path.pop_back();
                }
        }
    };

  • 0
    R

    complexity is O(VE)?


Log in to reply
 

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