Given a non-empty string $str$ and a dictionary containing a list of unique words, design a dynamic programming algorithm to determine if $str$ can be segmented into a sequence of dictionary words. If $str$ = "algorithmdesign" and your dictionary contains "algorithm" and "design". Your algorithm should answer Yes as $str$ can be segmented as "algorithmdesign". You may assume that a dictionary lookup can be done in $O(1)$ time.

1) We basically are required to find if s[0,n-1] can be segmented using words in dictionary.To solve this problem we will have to solve the problem like we will have to find if s[i,j] can be segmented into words of dictionary then we need to find an index k in between i and j such that s[i,k] and s[k+1,j] both can be partiotoned into words of dictionary this is recursively done for all such segments and finally results are merged back to get the requied answer.

2) let T[i,n-1] represent if substring from [i,n-1] can be segmented into words of dictionary.

T[i,n-1]=1 if substring s[i,k] is in dictionary and T[k+1,n-1] =1 for any k>=i&&k<=n-1

T[i,n-1]=0 otherwise

3) Pseudo Code

(i) input string

int T[n][n];

(ii) for i =n-1 to 0: do

(iii) for k=i to n-1: do

(iv) if s[i,k] is in dictionary:

(v) if (k==n-1||k<n-1&&T[k+1][n-1]==1):

(vi) T[i][n-1]=1

(vii) else:

(viii) T[i][n-1]=0

(ix) else:

(x) T[i][n-1]=0

(xi) return T[0][n-1]

4) time complexity is we are using two loops and a temporary array hence time complexity is o(n^2).

Explanation: