2
$\begingroup$

The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words return -1.

I tried finding the longest prefix and proceeding but that doesn't seem to work. I searched this question online and found a similar stack exchange question but I believe that the solution provided is wrong. It looks like this person is finding the longest suffix and proceeding but this approach doesn't work. Link to similar question

The reason this doesn't work is because: Suppose the dictionary is:{i,iiiiface,facebook,book} and input instance is 'iiiiifacebook'. The given solution would select 'facebook' and then continue to select 5 'i's' making a total of 6 words when infact the optimal solution is: (book,iiiiface,i) which is just 3 words. Please correct me if I'm wrong.

Please help me find the optimal (DP) solution to this problem.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Have you tried dynamic programming? cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W.♦ Oct 19 '19 at 3:11
  • $\begingroup$ Your question isn't completely clear. It seems to me that you are given a mapping $h\colon \Sigma \to \Delta^*$ and a string $y \in \Delta^*$, and your goal is to find a shortest string $x \in \Sigma^*$ such that $h(x) = y$. $\endgroup$ – Yuval Filmus Oct 19 '19 at 8:02
  • $\begingroup$ Just imagine u have a physical dictionary. And you have an arbitrary string: $x \in \Sigma^*$. if that string can be SPLIT into a list of meaningful words return the minimum possible splits (i.e: the minimum possible number of words). If the string can not be split into a list of meaningful words from the dictionary return -1 $\endgroup$ – Sid Oct 19 '19 at 12:40
1
$\begingroup$

One possible approach to solve this problem is as follows:-

(1) Create a trie of the dictionary for fast matching.

(2) Create a recursive function that does the following:-

(a) Finds all possible prefixes of the current string that are present in the dictionary.

(b) Calls itself recursively with those prefixes removed

Example:- 

Word:- keyboardrocks
Dictionary:- {key,keyboard,keyboardrock,s,board}

f(keyboardrocks)->f(boardrocks)
                ->f(rocks)
                ->f(s)

(c) Recurse until the string is reduced to an empty string.

(d) The minimum recursion depth will be the required answer.

What can be done to better the runtime complexity?

You can use memoization to remember the minimum number of words that were needed to construct a prefix of length m of the string in an array.

So now, MinWord[1,n]=MinWord[1,x]+findMinWord[x,n]
Improve this answer
$\endgroup$
0
$\begingroup$

Let the string be $S_1,\ldots,S_n$. For every $m$, find the minimum number of words that $S_1,\ldots,S_m$ can be split into. I'll let you work out the remaining details.

Improve this answer
$\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.