Algorithm/Insights
The given problem can be solved by using Dynamic Programming as described below:
1. Create a temporary boolean array validWords[] defined as:
validWords[i]
= true, if input substring from 0 to i forms valid words string
= false, otherwise
2. For i = 0 to input.length,
a. If input substring from 0...i is present in the dictionary, then set validWords[i] = true
b. If validWords[i] == true, from j = i+1 to n-1, check if substring from i+1 to j, for all values of j (= i+1 to n-1), is present in the dictionary and set validWords[j] to true if found in the dictionary.
3. When we reach the end of the string, if validWords[n-1] is true, then return true else return false.
Example:
Consider the dictionary:
Input string:
IDeservelearningplatform
Temporary array validWords[] initialized to false (represented by F in the image).
i = 0:
Is input substring from 0...i (= I) present in the dictionary? ✖
i = 1:
Is input substring from 0...i (= ID) present in the dictionary? ✖
i = 2:
Is input substring from 0...i (= IDe) present in the dictionary? ✖
Proceeding till i = 6:
Is input substring from 0...i (= IDeserv) present in the dictionary? ✖
i = 7:
Is input substring from 0...i (= IDeserve) present in the dictionary? ✔
Set validWords[i] = true (represented by T in the image)
Next, starting from j = i+1 to n-1, on checking for all substrings from i+1 to j, we see that 'learn' (ending at j=12) and 'learning' (ending at 15) form valid dictionary words.
So we set, validWords[12] = true and validWords[15] = true.
Since, we have not reached the end of the input string, we proceed with next steps.
i = 8:
Is input substring from 0...i (= IDeservel) present in the dictionary? ✖
Proceeding till i = 11:
Is input substring from 0...i (= IDeservelear) present in the dictionary? ✖
i = 12: input substring = IDeservelearn
validWords[i] is already true.
Next, starting from j = i+1 to n-1, on checking for all substrings from i+1 to j, we see that there is no valid dictionary word found.
Proceeding like before for i = 13 and 14:
Is input substring from 0...i (= IDeservelearni) present in the dictionary? ✖
Is input substring from 0...i (= IDeservelearnin) present in the dictionary? ✖
i = 15: input substring = IDeservelearning
validWords[i] is already true.
Next, starting from j = i+1 to n-1, on checking for all substrings from i+1 to j, we see that 'platform' (ending at 23) is a valid dictionary word.
So, we set validWords[23] = true.
Since, we have reached end of string and validWords[n-1] = validWords[23] = true, hence we return true.