C++ non recursive dp


  • 0
    G
    class Solution
    {	
    	struct hash { std::size_t operator() ( const std::string::const_iterator& obj ) const { 
    		static_assert( sizeof obj >= sizeof( std::uintptr_t ) , "" ) ;
    		return std::hash< std::uintptr_t >()( reinterpret_cast< const std::uintptr_t& >( obj ) ) ; } } ;
    	public:
    		std::vector< std::string > wordBreak ( std::string str , std::unordered_set< std::string > & words ) 
    		{
    			std::unordered_map< std::string::const_iterator , std::vector< std::string > , hash > map { { str.cend() , { "" } } } ; // chached
    			std::deque< std::string::const_iterator > beginings { str.cbegin() } ;
    			std::ptrdiff_t max_length {} ;
    			for ( const auto& each : words ) if ( max_length < each.size() ) max_length = each.size() ;
    			for ( auto last = beginings.back() ;  ;  )
    			{	
    				while ( last != str.end() && std::distance( beginings.back() , last ) != max_length )
    					if ( words.find( std::string( beginings.back() , ++ last ) ) != words.end() )
    						if ( map.find( last ) != map.end() ) 
    							for ( const auto& each : map[ last ] )
    								map[ beginings.back() ].emplace_back( std::string( beginings.back() , last ) + ( each == "" ? "" :  " " + each ) ) ; 
    						else beginings.push_back( last ) ;
    				last = beginings.back() , beginings.pop_back() ;
    				if ( beginings.empty() ) break ;
    				for ( const auto& each : map[ last ] )
    					map[ beginings.back() ].emplace_back( std::string( beginings.back() , last ) + " " + each ) ; 
    			}		
    			return map[ str.cbegin() ] ; 
    		}	
    } ;
    

Log in to reply
 

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