$2$ Morse Code $(3$pts$)$

In class we learned Morse Code. Because it is not a prefix code, we've seen that a code can be interpreted in several different ways. For example, $".-.-"$ can be interpreted as AA$,$ EK$,$ RT$,$ and so on$.$

We use $\backslash ($ s$[$c$]\backslash )$ to denote the number of strokes of a letter $\backslash ($ c $\backslash ).$ Here we only consider upper case letters. The number of strokes are also provided in the parentheses after each letter. There are of course multiple ways to handwrite a letter, and here I$\text{'}$m using a common version appearing in many letter written templates. For some reason, for the same morse code, we prefer those interpretations with fewer strokes.

Given a Morse code $\backslash ($ X $\backslash )($a string consisting of $.$ and $-),$ we want to know, among all the possible interpretations of $\backslash ($ X $\backslash ),$ which one uses the smallest number of strokes. For simplicity, assume we have a unit$-$cost function check $\backslash (($X$,$ i$,$ j$,$ c$)\backslash )$ that checks if the substring $\backslash ($ X$[$i $..$ j$]\backslash )$ is the Morse code for character $\backslash ($ c $\backslash ).$ For example, $\backslash (\backslash$operatorname$\{$check$\}($X$,2,5\backslash ),\text{'}$B$\text{'})$ checks if the second to the fifth character in $\backslash ($ X $\backslash )$ is $"-..."($the Morse code for $\text{'}$B$\text{'}).$

As an example, consider $\backslash ($ X$=\backslash )".-.-".$ There are many possible interpretations for $\backslash ($ X $\backslash )$ : AA $(6$ strokes$),$ EK $(5$ strokes$),$ RT $(4$ strokes$),$ ETET $(10$ strokes$),$ and so on$.$ The fewest strokes we can get is $4.$

$(1)(0\mathrm{.}5$pts$)$ What is the Morse code for word "UCR"? Is there any other interpretations of UCR's code $($if there's no separator$)?$ Please list at least three of them, and at least one of them should have length $\backslash (\backslash$leq $4\backslash ).$ Which of them have the fewest strokes?

$(2)(1\mathrm{.}5$pts$)$ Design an algorithm for the above task: given a Morse coding string $\backslash ($ X $\backslash ),$ find the one with the fewest strokes among all possible interpretations of $\backslash ($ X $\backslash ).($Hint: You can use $\backslash ($ f$[$i$]\backslash )$ to denote the fewest strokes you could get using first $\backslash ($ i $\backslash )$ elements in $\backslash ($ X $\backslash ).)$

$(3)(0\mathrm{.}5$pts$)$ What is the time complexity of your algorithm?

$(4)(0\mathrm{.}5$pts$)$ Use your algorithm to compute: what is smallest number of strokes you can get by interpreting string $"--..--."?$ Assume you only use the following letters A $(3$ strokes$),$ C $(1$ stroke$),$ E $(3$ strokes$),$ G $(2$ strokes$),$ K $(2$ strokes$),$ and T $(2$ strokes$).$