Breaking words.

When we type something hastily into a search box, we often mistype and leave out one or

more spacesbetweenwords. However, search engines are usually still able to search for what we

"meant" to type, in part by checking whether the input string can be split into words from a

dictionary. Using the power of dynamic programming, you will design an algorithm that does

this!

$($a$)$ We want an algorithm Word$-$Break$(S,L),$ where $S$ is a string and $L$ is a list of words. It

should return true exactly when $S$ is the concatenation of a sequence of words from $L$

$($the words in $L$ are distinct and non$-$empty; each may appear zero, one, or many times

in $S).$ Here are a few examples:

Input: 'EECS', $\text{'}376\text{'},\text{'}$Is$\text{'},$ 'Awesome'$],S=$ 'Awesome$376$IsAwesome'.

Output $=$ true.

Input: $L=[\text{'}$cats$\text{'},$ 'and', 'dogs'$],S=$ 'catsanddogs'.

Output $=$ true.

Input: $L=[\text{'}$cats$\text{'},$ 'and', 'dogs'$],S=$ 'catsandogs'.

Output $=$ false.

Input: $L=[\text{'}$cats$\text{'},$ 'and', 'dogs', 'cat', 'sand'$],S=$ 'catsand'.

Output $=$ true.

Derive, with justification, a recurrence relation $($including base case$($s$))$ that is suitable for

a dynamic$-$programming implementation of Word$-$Break. Your recurrence may rely on

a 'lookup' function $L(w)$ that outputs true if winL, and false otherwise.

$[$

$($b$)$ Fill in a table containing all the relevant values of your recurrence for the input

$S=$ 'catsand', $L=[\text{'}cat\text{'},$ 'cats', 'sand', 'and'$].$

Describe the order in which you filled the table, and the criteria you used to decide which

already$-$filled cell$($s$)$ to consult as you filled each cell.

$($c$)$ In the fourth example above $($in which $S=$ 'catsand'$),$ the correct output is true, and in

fact there are two sequences of words from $L$ that can be concatenated to form $S.$ Modify

your original recurrence so that instead of outputting a true$/$false value, it outputs how

many ways $S$ can be expressed as a concatenation of words from $L.$ For this purpose, you

may modify the lookup function so that $L(w)=1$ if winL, and $L(w)=0$ otherwise.