Dynamic Programming - Decision Procedures, and Optimizations Part 2
In a similar vein to our summing problems from last week, we are tweaking our approach to tackle string construction. Our decision procedure will be an algorithm that determines whether a word can be constructed from a array bank of strings.
For example if we want to construct the word skateboard using the bank of strings [“bo”, “rd”, “ate”, “t”, “ska”, “sk”, “boar”] we can construct a recursive tree to test each element in the array. Our initial branches will have to be a prefix of the original word, so in our case “ska”, or “sk”, and then we would test the remaining elements until we return a base case of an empty string (meaning we have constructed our word), or we end up with a string that we can no longer remove a prefix from.
Our recursive function would look something like this:
Javascript strings have a prototype method indexOf() that we can use to determine if the search term is in the string, and return the starting index, and combined with the slice() method we can also create our suffix like in our tree.
By now we realize that the our time complexity (our branches we have to check) can be in the worst case, each element of the word bank n. Our maximum length of the tree would similarly depend on the length of the target m, so at each node we potentially have to check n branches for the entire length of m that results in O(nm) time. We also create a new suffix in each of our loops so ultimately our worst time complexity is O(nm * m).
Make it dynamic
We can make this a little faster by introducing a memo object, and potentially save from repeatedly making the same recursive calls.
Instead of brute force time complexity of O(nm * m), we now only have to calculate a maximum of n branches. We do add an additional memo object in addition to the sliced variable so ultimately our time complexity is O(n * m2)
Slight Tweak to Count Combinations
Our canConstruct decision procedure can also then be tweaked to give us the total number of combinations that can construct our target word.
Keeping track of the combinations
Similar to our countConstruct (and the howSum solution from last week), we can apply an additional variable and return the total combinations that can construct our target word. As we recursively test our combinations we can store the elements in an array and return that instead of the total count.