Monthly Archives: December 2015

Given a dictionary, and a string, find is string can be broke down by words in dictionary.
For example, dict = [cat, cats, and, dog, sand], str=’catsanddog’
Should return ‘cat sand dog’, ‘cats and dog’

Naive way is from-top-to-bottom.
For example, if we want to check [c1, c2, c3, c4, c5] is breakable, we check c[1,…,j] and c[j+1,…,5] where j=1, 2, 3, 4

Another way is from-bottom-to-top:
Check if [c1], [c2], [c3], [c4], [c5] are breakable.
Check if [c1, c2], [c2, c3], [c3, c4], [c4, c5] are breakable.
Check if [c1, c2, c3], [c2, c3, c4], [c3, c4, c5] are breakable.
Check if [c1, c2, c3, c4], [c2, c3, c4, c5] are breakable.
Finally, check if [c1, c2, c3, c4, c5] is breakable.

A better way is similar to minimum coin problem. link
Use an auxiliary array breakable[]. breakable[i] indicates if [c1,…,ci] is breakable.
Set a pointer moving from left to right, the process is like below:

Based on that, my code print all the possible breakdown options. Check here: link

Given a set of coins and a bill value, use minimum number of coins to consist of number.
For example, coin = {1, 2, 5}, bill=11. the minimum coins is 5+5+1=11, 3 coins
coin = {1, 2, 5}, bill=11, the minimum coins is 1+1+1+1+1+1+1+1+1+1+1=11, 11 coins
coin = {2, 5, 7}, bill=11, there is no valid combinations, return -1
coin = {2, 5, 7}, bill=10, minimum is 2+2+2+2+2=10, 5 coins

This problem is DP problem which is quite similar to 0-1 knapsack problem. First of all, we put all coins in coin[] array. The coin should be in ascending order. The formula is below. dp[i][j] means the minimum number of coins when we only use coin[0], coin[1], …, coin[i] to combine bill j.

When j is less than coin[i], then dp[i][j] equals dp[i-1][j]. When j is equal or greater than coin[i], first we use one coin coint[i], then we should find the min number of j-coin[i], whose result we already got and is dp[i][j-coin].

Take coin={1, 2, 5}, bill=11 for example.
The dp array is like below:

So the result is dp[2][11]=3

Take coin={2, 5, 7}, bill=11 for example.
The dp array is like below:

So the result is dp[2][11]=3. Another thing which we should notice is that the number of coins consisting 10 is 2, not -1.

The time complexity O(n*b), space complexity is O(b). n is number of coins, b is bill value.

Here is my code on github: link