algorithm to parse string with dictionary

Given

a dictionary full of words {in, july, den, dentist, best, ...} with some C++ API to access it: boolean findWord(string word), or string getNextWord(void) to iterate through it,
some input string with no space, e.g.: bestdentistinjuly...

Output

best dentist in july is... (basically separate the non-space string by space given a dictionary)

What will be the best algorithm to solve it?

A subtle but important question is, is there any fancy way to solve the unreachable dead-end problem. E.g., den and dentist are both valid words to dissect the rest of the string, one of them may just be a dead-end.

To me it seems like a greedy problem or something solvable by dynamic programming..

Edit Report

1 Answer

Maybe there are more than one valid solutions to separate the input string. You could use a backtracking algorithm to just find one or all valid solutions. On positions where two or more words e.g. "den", "dentist" are possible, the algorithm should try the longer words first.

The dictionary of course should be stored into a Trie to quickly find the matching words.

In the following ascii image the left branch would be examined first in a Depth-first search which prefers longer words. A solution would be found before the algorithm looks at the right branch with the word "den".


        Best
        /   \
   dentist  den
      /
     in
    /
  july

answered 2011-07-20T18:47:55.487

algorithm to parse string with dictionary

1 Answer

Your Answer