JavaScript solution beat 100%


  • 0
    A
    var shoppingOffers = function(price, special, needs) {
        var result = Number.MAX_SAFE_INTEGER;
        
        special = special.filter((offer) => {
            let retailPrice = 0;
    
            for(let i=0;i<offer.length-1;i++) {
                retailPrice += offer[i] * price[i];
            }
            
            return retailPrice >= offer[offer.length-1];
        });
        
        function addToResult(price) {
            result = Math.min(result, price);
        }
        
        dfs(price, special, needs, 0, addToResult);
        
        return result;
    };
    
    
    function dfs(price, offers, target, currentPrice, cb){
        var availbleOffers = offers.filter((offer) => {
            for(let i=0;i<target.length;i++) {
                if(offer[i] > target[i]) return false;
            }
            
            return true;
        });
        
        if(!availbleOffers.length) {
            for(let i=0;i<target.length;i++) {
                currentPrice += target[i]*price[i];
            }
            
            cb(currentPrice);
            
            return;
        }
        
        for(let offer of availbleOffers) {
            let afterPick = [];
            
            for(let i=0;i<target.length;i++) {
                afterPick.push(target[i] - offer[i]);
            }
    
            dfs(price, availbleOffers, afterPick, currentPrice + offer[offer.length-1], cb)
        }
        
    }
    
    

Log in to reply
 

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