算法解析字符串字典

问题描述

由于

• 字典言语， {中，七月，书房，牙医，最好的，...} 有一些C ++的API来访问它：布尔findWord（串词）或字符串getNextWord（无效）来遍历它，

• 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,

有没有空间，如一些输入字符串： bestdentistinjuly ...

some input string with no space, e.g.: bestdentistinjuly...

输出

• 最好的七月是牙医... （基本上由分开的空间，非空字符串给出一个字典）

• 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..

推荐答案

您可以创建一种单词树的：

You can create a kind of word tree:

您可以去throught的字符串没有空间。一旦你发现在你的列表中的单词，你添加一个空格，然后再continu ......直到你不能走的更远。

You can go throught the string with no space. Once you find a word in your list, you add a space and you continu... until you cannot go further.

然后你回到previous词，并尝试本身，如果增加新的字母，您可以创建一个字，如果你可以从他们的。continu

Then you go back to the previous word and try to se if adding new letter you can create a word, and if you can continu from their.

您试试这个，直到你尝试了所有的possiblities。

You try this until you tried all the possiblities.

如果你回到起始字，你没有找到任何解决方案=>无溶胶

If you go back to the starting word and you don't find any solution => no sol

下面是该算法（我的伪code语法不好，但你可以得到的总体思路，我相信你将不得不修正了一点。）：

TreeWordResult //Tree that keeps the results in memory

Go through the InputString:

      If you find a word in the InputDictionnary
          Then add this word to the last node of the treeWordResult
      Otherwise:
          while (No word found):
                go back in the treeWordResult
                try to find word in InputDictionnary different from the one before (on the other node)
          endwhile
          if no word found:
                     return NO SOLUTION
          otherwise:
                     continue going through word
          endif
       endif
 return Leaf

算法结束，当你发现没有溶胶，或当你在叶子（你去thhrough整个字符串）

Algorithm ends when you find no sol, or when your at a "leaf" (you went thhrough the whole string)

下面是使用示例的图示：

希望我的解释是明确的。

Hope my explaination is clear.

这篇关于算法解析字符串字典的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！