Dfs with multimap solution gets TLE


  • 0
    K

    The concept is to generate a string to string multimap for finding possible next steps.
    If there is a string "abc" in the dict, the following entries are to be inserted to the multimap.

    "Xbc"->"abc", "aXc"->"abc", "abX"->"abc".

    However this approach gets TLE.

    class Solution {
    public:
        typedef unordered_multimap<string, string> strmap_t;
        
        vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
            strmap_t mm;
            pair<string, string> entry;
            for(auto it=dict.begin(); it!=dict.end(); ++it)
                add_entry(*it, mm);
            add_entry(end, mm);
            vector<vector<string>> ret;
            vector<string> transform;
            unordered_set<string> visited;
            dfs(ret, transform, start, end, mm, visited);
            return ret;
        }
        
        //add all possible entries of a string to the string map. in the form of 'Xb'->'ab', 'aX'->'ab'
        void add_entry(string str, strmap_t &mm)
        {
            pair<string, string> entry(str, str);
            size_t len = str.length();
            for(size_t i=0; i<len; i++)
            {
                char prev = str[i];
                entry.first[i] = 'X';
                mm.insert(entry);
                entry.first[i] = prev;  //recover string
            }
        }
        
        void dfs(vector<vector<string>> &ret,
                 vector<string> &transform,
                 string start, string end, 
                 strmap_t mm,
                 unordered_set<string> &visited)
        {
            if ((!ret.empty()) && ret.front().size()<transform.size())
                return;
            transform.push_back(start);
            if (start==end)     // find the transform
            {
                if (ret.empty()
                    || ret.front().size() == transform.size())
                    ret.push_back(transform);
                else if (ret.front().size() > transform.size())
                {
                    ret.clear();
                    ret.push_back(transform);
                }
            }
            else
            {
                visited.insert(start);  // mark the visit
                for (size_t i=0; i<start.length(); i++)
                {
                    char prev = start[i];
                    start[i] = 'X';
                    auto range = mm.equal_range(start); // find possible next steps
                    for_each( range.first,
                              range.second,
                              [=, &ret, &transform, &visited](strmap_t::value_type s)
                              {
                                if (visited.find(s.second) == visited.end())    //if not visited
                                    dfs(ret, transform, s.second, end, mm, visited);
                              }
                            );
                    start[i] = prev;
                }
                visited.erase(start);
            }
            transform.pop_back();
        }
    };

Log in to reply
 

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