Accepted C++ code with ~ 327ms running time


  • 0
    P
    class Solution 
       {
          void find_paths(string curr, string target, vector<string> &path, int max_dist,
    		  vector< vector<string> > &res,		  
    		  unordered_map< string, unordered_set<string> > &search_graph)
      {
        if ( max_dist < 0 ) return;
        if ( curr == target )
          {
    	path.push_back(target);
    	res.push_back(vector<string>(path.rbegin(), path.rend()));
    	path.pop_back();
    	return;
          }
    
        path.push_back(curr);
        auto &neighbors = search_graph[curr];
        for ( auto wt = neighbors.begin(); wt != neighbors.end(); ++wt )
          find_paths(*wt, target, path, max_dist - 1, res, search_graph);
        path.pop_back();
      }
      
    public:
      vector< vector<string> > findLadders(string start, string end, unordered_set<string> &dict)
      {
        vector< vector<string> > res;
        if ( start.size() != end.size() ) return res;
    
        unordered_map< string, unordered_set<string> > search_graph;
    
        int min_dist = INT_MAX;
        queue< pair<string, int> > word_queue;
        word_queue.push( pair<string, int>(start, -1) );
        
        for (int dist = 1; dist < min_dist && ! word_queue.empty() && ! dict.empty(); ++dist)
          {
    	int num_elems = word_queue.size();
    	for (; num_elems > 0; --num_elems)
    	  {	    
    	    auto wip = word_queue.front(); word_queue.pop();
    	    const string &word = wip.first;
    	    const int idx = wip.second;
    	    dict.erase(word); // only need the closest visit to the word
    	    
    	    int len = word.size();
    	    bool stop_search = false;
    	    string next_word = word;
    	    
    	    for (int i = 0; i < len && ! stop_search; ++i)
    	      {
    		if ( i == idx ) continue;
    		
    		for (char ch = 'a'; ch <= 'z' && ! stop_search ; ++ch)
    		  {
    		    if ( word[i] == ch ) continue;
    		    next_word[i] = ch;
    
    		    bool target_matched = (next_word == end);
    		    if ( target_matched )
    		      {
    			min_dist = dist;
    			// From any word there is only one mutation
    			// to match any other word, thus once the
    			// end word is found, break the search of
    			// the current word.
    			stop_search = true; 
    		      }
    
    		    if ( target_matched || dict.count(next_word) > 0 )
    		      {
    			if ( search_graph.count(next_word) == 0 )
    			  word_queue.push( pair<string, int>(next_word, i) );
    			search_graph[next_word].insert( word );
    		      }
    		  }
    		next_word[i] = word[i];
    	      }
    	  }
          }
    
        if ( min_dist != INT_MAX )
          {
    	vector<string> path;
    	find_paths(end, start, path, min_dist, res, search_graph);
          }
        return res;
      }
        
    };

Log in to reply
 

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