从损坏的字符串构造原始字符串

Question

我收到了一个损坏的字符串,其中包含错误位置的空格和包含正确单词的字典.挑战是使用字典构造原始字符串.

For example : 
Dictionary : ["how","are","you"]
Corrupted String : ho ware y ou
Original String : how are you

我正在考虑一种递归方法,因为每个字符都有两种可能性,它可以是一个新单词或前一个单词的一部分.我正朝着正确的方向前进吗？这个问题有更好的方法吗？

Answer 1

您应该删除所有空格，然后将字典中的单词与字符串的头部进行匹配，并递归地检查字符串的尾部是否可以以相同的方式匹配。您希望递归函数返回所有匹配项，例如匹配的字符串数组或树。我刚刚将其写入下面的打印输出，但您可以改为存储输出。

printAllMatches(String head, String tail)
  if tail.equals("") print head and return
  for each word w in dictionary
    if w matches beginning of tail
      printAllMatches(head + " " + w, tail - w) // remove w from front of tail

然后您可以通过 调用该函数printAllMatches("", stringWithoutSpaces)。当 的前面stringWithoutSpaces得到处理时，它会转移到head。