Problem $2.$ You are given an array of characters S$[1$ : n$]$ such that each S$[$i$]$ is a small case letter from the

English alphabet. You are also provided with a black$-$box algorithm dict that given two indices i$,$ j in $[$n$],$

dict$($i$,$ j$)$ returns whether the sub$-$array S$[$i : j$]$ in array S forms a valid word in English or not in O$(1)$ time.

$($Note that this algorithm is provided to you and you do not need to implement it in any way$).$

Design and analyze a dynamic programming algorithm to find whether the given array S can be partitioned

into a sequence of valid words in English. The runtime of your algorithm should be O$($n$2).$

Example: Input Array: S $=[$maythef orcebewithyou$].$

Assuming the algorithm dict returns that may, the, f orce, be$,$ with and you are valid words $($this means that

for instance, for may we have dict$(1,3)=$ True$),$ this array can be partitioned into a sequence of valid words