3
$\begingroup$

I am given a input string $s$ ("bedbathandbeyond") and a set of words {"bed", "bath", "beyond", "bat", "hand", "and"}. I need to divide the input string $s$ into a series of words in the dictionary. In this case, the two allowed outputs would be ["bed", "bath", "and", "beyond"] and ["bed", "bat", "hand", "beyond"]. Both outputs are allowed and none is better than the other.

Here is my recursive solution. On input $s$, it either outputs a decomposition of $s$ into a sequence of words in the dictionary, or Fail.

  • If the input $s$ is empty, output the empty decomposition.
  • Otherwise, go over all prefixes of $s$. For each prefix that belongs to the dictionary, recursively try to decompose the corresponding suffix, and if successful, output the corresponding decomposition.
  • If no decomposition was found, output Fail.

In order to speed up the procedure, I envision using memoization. That is, I maintain a hashtable with answers to previous queries, and on input $s$, I first check whether I already know the answer for $s$. If not, after computing the answer, I put it in the hashtable.

If no memoization is used, the runtime is clearly exponential: we have $O(n)$ branching factor, and $O(n)$ as the depth: $O(n^n)$. With memoization; however, the algorithm seems to be polynomial: the procedure can be called with at most $n$ different inputs, and it then performs a polynomial amount of work on it.

I've been told by a very knowledgeable person that it's still exponential. Could someone explain why? I've been thinking very hard about it and I'm not sure why that's the case. If it matters, I'm implementing this algorithm in python.

$\endgroup$
2
  • 1
    $\begingroup$ Please add pseudocode instead of the python code. Some of us might not know the syntax of python. $\endgroup$ May 13 at 2:44
  • $\begingroup$ (Also on SO) $\endgroup$
    – greybeard
    May 14 at 17:51
3
$\begingroup$

The running time is polynomial with memoization. If the original input string has $n$ characters, then there are only $O(n)$ possible suffixes of the original string, the function is only called on a suffix of the original string, and (ignoring recursive calls) the time to execute the function is polynomial; so the total running time with memoization is polynomial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.