[c++]share two solutions with 200ms and 79ms


  • 0
    X

    first 200ms,second 79ms
    In fact, these are the same idea,but different data structure

    class Solution {
    	public:
    		vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
                wordList.erase(beginWord);
    			wordList.erase(endWord);			
                rest = wordList;            
    			front.insert( beginWord );
    			back.insert( endWord );	
    			while( !combine() ) 
    		        if(!buildLevel( front.size()<=back.size() ))
    		            return ladders;
    			findPath(beginWord,endWord);
    			return ladders;
    		}
    	private:
    		vector<vector<string>> ladders;
    		vector<string> ladder;
    		map<string,vector<string>> tree;
    		unordered_set<string> front,temp,back,rest; 		
            unordered_set<string> *pSrc,*pTar;
            
    		void findPath(string& node,const string& end_word) {
    			ladder.push_back(node);
    			if( node == end_word )
    				ladders.push_back(vector<string>(ladder));
    			else
    				for( string child:tree[node] ) 
    					findPath(child,end_word);
    			ladder.pop_back();
    		}		
    		bool combine(){
    		    bool ret =false;
    	    	for( string src : front ) 
    				for( string tar : back ) 
    					if( isNeighbor(src,tar) ) 
    					    ret= true;
    		    return ret;
    		}
    		bool buildLevel(bool forward){
    			pSrc = forward?&front:&rest;
    			pTar = forward?&rest:&back;
    			for( string src : *pSrc ) 
    				for( string tar : *pTar ) 
    					if( isNeighbor(src,tar) ) 
    						temp.insert(forward?tar:src);
    			if( temp.empty() )	return false;
    	    	for(string word:temp)
    		        rest.erase(word);
    			pSrc = forward?&front:&back;
    			pSrc->clear();
    			swap( *pSrc,temp );
    		    return true;
    		}
    		bool isNeighbor(const string& word1,const string& word2) {
    			bool ret = false;
    			for(int i=0,len=word1.size();i<len;i++)
    			    if( word1[i] != word2[i] )
    			        if( ret ) return false;
    			        else ret = true;
    			tree[ word1 ].push_back( word2 );
    			return ret;
    		}
    };
    

    second

    class Solution {
    	public:
    		vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {
    			wordList.erase(beginWord);
    			wordList.erase(endWord);
    			
    			last = wordList.size()+1;
    		    words = new string[last+1];
                tree = new vector<int>[last+1];
                
                //front_begin,front_end,back_begin,back_end,temp_end;
                fb=0,fe=1,bb=last,be=last-1,te=1;
                words[fb] = beginWord;
                words[bb] = endWord;
                
                for( string word : wordList )
                    words[te++]= word;
    
    			while( !combine() )
    		        if(!buildLevel( (bb-be)-(fe-fb)>0 ))
    		            return ladders;
    
    			findPath(0);
    
    			return ladders;
    		}
    	private:
    		vector<vector<string>> ladders;
    		vector<string> ladder;
    		vector<int> *tree;
    		int fb,fe,bb,be,te,last;//front_begin,front_end,back_begin,back_end,temp_end,last;
    		string *words;
    		
    		void findPath(const int& w) {
    			ladder.push_back(words[w]);
    			if( w == last )
                    ladders.push_back(vector<string>(ladder));
                else
                    for( int child:tree[w] )
    				    findPath(child);
    			ladder.pop_back();
    		}
    		
    		bool combine(){
    		    bool ret =false;
    	    	for( int i=fb;i<fe;i++ ) 
    				for( int j=bb;j>be;j-- ) 
    					if( isNeighbor(words[i],words[j]) ){ 
    					    ret= true;
    					    tree[ i ].push_back( j );
    					}
    		    return ret;
    		}
    		bool buildLevel(bool forward){
    		    if( forward ){
    		        te = fe;
    		        for(int i=fb;i<fe;i++){
    		            for( int j=fe;j<=be;j++){
    		                if( isNeighbor(words[i],words[j]) ){
    		                    if( j < te){
    		                        tree[ i ].push_back( j );
    		                    }else{
        		                    swap( words[j],words[te] );
        			                tree[ i ].push_back( te++ );
    		                    }
    		                }
    		            }
    		        }
    		        if( te== fe) return false;
    		        fb=fe,fe=te;
    		    }else{
    		        te = be;
    		        for(int i=bb;i>be;i--){
    		            for( int j=be;j>=fe;j--){
    		                if( isNeighbor(words[i],words[j]) ){
    		                    if( j>te ){
    		                        tree[ j ].push_back( i );
    		                    }else{
        		                    swap( words[j],words[te] );
        			                tree[ te-- ].push_back( i );
    		                    }
    		                }
    		            }
    		        }
    		        if( te== be) return false;
    		        bb=be,be=te;		        
    		    }
    		    return true;
    		}
    		bool isNeighbor(const string& w1,const string& w2) {
    			bool ret = false;
    			for(int i=0,len=w1.size(); i<len ; i++)
    			    if( w1[i] != w2[i] )
    			        if( ret ) return false;
    			        else ret = true;
    			return ret;
    		}
    };
    

Log in to reply
 

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