Is Writable

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.

Example 1:

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

Example 2:

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

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

First Few Test Cases:

We want to return whether the given string is writable.

1. Recursion

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:

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:

2. Base case

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

3. Code

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:

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

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

Mark as Completed:
Test your code to get an output here!
Test your code to get an output here!