Valid phrases from text.

You have given a dictionary and a string, you need to separate words that are in dictionary.
ex - catsanddog (here cat and cats both can be in dictionary)
output - cats and dog


Approach:
1. Lets say the length of the string is n and init phrase String as empty.
2. Now for every substring S[i,j] (0<=i<=j<n), check if its a valid word - check against the dictionary.
3. If we get a valid word then append it to the previously calculated and running phrase with a space.


Code input/output:
Input String: catsanddog
valid phrases:
[cats and dog]