Put Spaces in a String.

Let's say you have a phrase without any spaces - eg. "thisisawesome". Given a dictionary, how would you add spaces in this string?


OR


When people search at Google, they often type two words without space. For example, instead of typing "binary tree", someone can type "binarytree". Given an input, what is a good way of finding if it is a combination of two valid words?


Input:
thisisaninterestingsentence
Output:
this is an interesting sentence


Approach for the phrase problem:
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.


Approach for the "two words wothout the space" problem.
1. Split the given string S[0..n] at the i (0<=i<n) positions. - For every split at ith index you will get 2 substrings S[left] and S[right]
2. Check if S[left] and S[right] are valid words.