BFS short solution java


  • 0
    V
    public class Solution 
    {
        int cnt;
        boolean isSet;
        public int coinChange(int[] coins, int amount) 
        {
            if(amount == 0)
                return 0;
            isSet = false;
            HashSet<Integer> hs = new HashSet<Integer>();
            cnt = 0;
            hs.add(amount);
            while(hs.size() > 0 && !isSet)
            {
                cnt++;
                HashSet<Integer> tempHs = new HashSet<Integer>();   
                Iterator<Integer> it = hs.iterator();
                while(it.hasNext() && !isSet)
                {
                    int t = it.next();
                    it.remove();
                    for(int i = 0; !isSet && i < coins.length; i++)
                    {
                        if(t - coins[i] == 0)
                            isSet = true;
                        else if(t - coins[i] > 0)
                            tempHs.add(t - coins[i]);
                    }
                }
                hs = tempHs;
            }
            return isSet? cnt: -1;
        }
    }

Log in to reply
 

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