Ruby BFS


  • 0
    D
    def coin_change(coins, amount)
        return 0 if amount == 0
    
        map = Hash.new(false)
        a = [[amount, 0]]
        coins = coins.sort.reverse
        count = 0
        
        while !a.empty? do
            r = a.shift
            coins.each do |coin|
                sub_amount = r[0] - coin
                return r[1] + 1 if sub_amount == 0
                next if sub_amount < 0
                unless map[sub_amount]
                    map[sub_amount] = true
                    a << [sub_amount, r[1] + 1]
                end
            end
        end
        -1   
    end
    

Log in to reply
 

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