Given a string of characters s₁s₂ . . . s_n. It is believed that the string is English sentences in which all spaces and punctuations have been removed. The following methods can be used to insert spaces back into the document.

(a) Constructed a graph from the string s₁s₂ . . . s_n and then find a path in the graph.

(b) Solve the problem by dynamic programming.(sub problem , pseudo C code )

Use the following string wewillmeetatmidnight to explain the above two methods. You may assume that the only words are

a at me meet mid midnight night we will