Solve the following problems by reducing to a DAG shortest (or longest) path problem. You should be explicit about how you use the given input to algorithmically generate an adjacency list and edge weights and which vertices you are finding a shortest (or longest) path between.

Suppose that you have constant-time access to a dictionary of valid English words, i.e., the function Dict(w) = { true if w is a valid word false otherwise} takes O(1) time. Design an O(n^2)-time algorithm to determine whether any given n-letter string s can be decomposed into a sequence of valid English words. For example, your algorithm should return true on input s = "iwastheshadowofthewaxwingslain" and false on input s = "bythfalseazureinthewindowpane".

We regard strings as simple arrays of characters. In particular, you can access the ith character s[i] in O(1) time, and you can append a character to the end of a string in O(1) amortized time, but retrieving an arbitrary substring s[i..j] would take O(j i) time.