Suppose we have some text as a series of a number of characters and a dictionary consisting of some words that are sub-strings of the text, $D=\{w_1,w_2,\dots,w_n\}$. The dictionary is rich enough so we can write the text by joining words from it. How can we write the text using the minimum number of words from the dictionary (possibly more than once) ? (other than the obvious of finding all combinations of words and choosing the minimum which by the way I don't know how to do... I appreciate


Suppose the text is $$ T=\{c_1,c_2,\dots,c_m\}, $$ where the $c_i$ are the text characters. Determine the maximal $k$ so that the word $w=\{c_1,c_2,\dots,c_k\}$ is in the dictionary. If $k=m$ there is just one word which is the whole text, so just use that and we 're done. If not, mark down that this word has been used, remove $w$ from the beginning of the text and keep doing that until there are no more characters left. It seems that LOCALLY this is the optimal algorithm but there is no guarantee that it's also GLOBALLY optimal. What to do now?


1 Answer 1


Build a graph with nodes $n_0$ to $n_m$ and an edge connecting $n_i$ to $n_j$ if the word $(c_{i+1} c_{i+2} \ldots c_{j}) \in D$. Then you just need to find the shortest path from $n_0$ to $n_m$ using Dijkstra's algorithm or one of its modifications (e.g. A*).

As an implementation note, the graph building may benefit from converting the representation of $D$ into a trie.


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.