Given a word of length n and n five-sided dice with a character on each side. Find out if this word can be constructed by the set of given dice. Example 1 Input: word = "hello" dice = [[a, l, c, d, e], [a, b, c, d, e], [a, b, c, h, e], [a, b, c, d, o], [a, b, c, l, e]] Output: true Explanation: dice[2] + dice[1] + dice[0] + dice[4] + dice[3] Example 2 Input: word = "hello" dice = [[a, b, c, d, e], [a, b, c, d, e], [a, b, c, d, e], [a, b, c, d, e], [a, b, c, d, e]] Output: false Example 3 Input: word = "aaaa" dice = [[a, a, a, a, a], [b, b, b, b, b], [a, b, c, d, e], [a, b, c, d, e]] Output: false (a) Frame this problem as a network flow problem; Give a graph showing the nodes with sources and sinks and give a rationale for your formulation. (b) To implement this, what algorithm(s) would you use? What is the running time of the algorithm? Why does it work (You can use exchange arguments to provide a proof)
Given a word of length n and n five-sided dice with a character on each side. Find out if this word can be constructed by the set of given dice.
Example 1 Input: word = "hello" dice = [[a, l, c, d, e], [a, b, c, d, e], [a, b, c, h, e], [a, b, c, d, o], [a, b, c, l, e]]
Output: true
Explanation: dice[2] + dice[1] + dice[0] + dice[4] + dice[3]
Example 2 Input: word = "hello" dice = [[a, b, c, d, e], [a, b, c, d, e], [a, b, c, d, e], [a, b, c, d, e], [a, b, c, d, e]]
Output: false
Example 3 Input: word = "aaaa" dice = [[a, a, a, a, a], [b, b, b, b, b], [a, b, c, d, e], [a, b, c, d, e]]
Output: false
(a) Frame this problem as a network flow problem; Give a graph showing the nodes with sources and sinks and give a rationale for your formulation.
(b) To implement this, what
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
