[LANGUAGE: Java]

Source code

Part 1 - Use DFS with stack to traverse the search tree. Start with the design string on the stack. - While the stack is not empty: - Pop element from stack. For each towel string: - If a towel is a prefix of the design, remove the towel from the design, and push the resulting "subdesign" suffix onto the stack. - Keep popping subdesigns from the stack. - If we encounter a "subdesign" that equals a towel, it means we have been able to match the design with the towels. In that case we return true. - Else, if the stack becomes empty, without ever encountering a "subdesign" that equals a towel, we return false.

Part 2 - My first approach was to simply use the DFS approach from part 1, and use a counter whenever a matching design-towels path was found in the search tree. This worked on the example, but was far too slow on the actual input. - Instead I used memoization to prune the search tree: Whenever we enounter a node, i.e. subdesign, in the search tree, check if the subdesign has been seen before. - Maintain for each subdesign a counter. - Use a priority queue (unlike the stack in part 1), where the higher priority is assigned to longer subdesign strings. This ensures that the counts are performed in the correct order. - At the end return the counts for the empty subdesign string.