The problem statement is, You are given a string and an array of some words. All the words are substring of the given string. You have to find all the ways to construct the string from the words of the array.
Suppose you are given a string "abcdef" and an array={ab,abc,cd,def,abcd}; here only one way to construct the string is ="abc+def"
my code prints all the ways. But it is really inefficient. it prints the same path multiple times if exists. It visits all the nodes. I want suggestions to memoize it so that it doesn't visit the same path if it visited it before. Can someone help me?
here is my code: https://github.com/Shuvro-d/Dynamic.Programming/blob/main/test.cpp
Try to think how many methods are to construct the substring [1..i], for 1 <= i <= n, where n is the length of the string?
Let's define the following recurrence: DP(0) = 1 (there is a way to construct the word!); DP(i) = sum {DP(k — 1), such that the substring [k, i] forms a word from that array, 1 <= k <= i}, for 1 <= i <= n;
This is the method for finding the NUMBER of solutions.
The only method to find ALL the solutions is to use brute-force, using that recurrence + one more parameter for saving your solution. It is guaranteed that no solution will repeat.