Is Writable


-----problem-----


You're trying to write a letter to a friend, but you can only print out certain strings. Return whether you can write a string `p` using the given strings `strings`.


\b{Example 1:}


$$
\def\l#1{& \texttt{#1} }
\begin{align*}
\l{p = "hibyehi"} \\
\l{strings = ["hi", "bye"]} \\[4bp]

\l{=> returns true}
\end{align*}
$$

\b{Example 2:}
$$
\def\l#1{& \texttt{#1} }
\begin{align*}
\l{p = "hibyehibyeye"} \\
\l{strings = ["hi", "bye", "eye"]} \\[4bp]
\l{=> returns false}
\end{align*}
$$

\b{Explanation:} The computer can't write the last part of the string "byeye" using the given strings.



-----solution-----


We want to return whether the given string is writable.
``
isWritable(p)
``

\s2

To check this, the idea is to chop one of the writable strings off of the start of `p`, and check if the remaining string is writable. Here's the recursion for this:



``
isWritable(p) = (
    chopped = []

    for s in strings:
        # if start of `p` equals a string, chop the string off
        if p[:len(s)] == s:
            chopped.append(p[len(s):])
        
    # return whether any remaining string is writable
    return any(isWritable(c) for c in chopped)
)
``


The above code is slow, since strings are immutable, and this will end up creating a new string in every chop. To optimize this, we can change our recursion to be on numbers instead of strings, by noticing that `isWritable` only ever chops off the left side of the string. This means we can write the recursion like this instead:
``
# returns whether `p[i:]` is writable
isWritable(i) = (
    idxs = []
    for s in strings:
        if p[i:i+len(s)] == s:
            idxs.append(i+len(s))
        
    return any(isWritable(idx) for idx in idxs)
)
``

\s3

The string keeps getting smaller until it's the empty string `""`, which is trivially writable:

``
isWritable(len(p)) = True
``


\s4



To avoid making redundant function calls, we should use Dynamic Programming. 

We can use "Tabulation", and compute all of the function calls in the order that they're needed. To do this, you should realize that `isWritable(i)` depends on `isWritable(bigger i)`, which means we can compute function calls on bigger `i` first and smaller `i` last. We'll store all the function calls in an array. Here's the code:

\answer

\tc $O(|\text{p}| \cdot |\text{strings}|)$. We iterate through all the letters in the string $\text p$, and for each letter, we iterate through all the strings in $\text{strings}$.

\sc $O(|\text{p}| + |\text{strings}|)$. We need to store the `isWritable` array, which grows to size $|\text{p}|$, and at the same time, we might also need to store the `idxs` array, which grows to size $|\text{strings}|$.




Recursion

Is Writable