algorithm - 使用字典将一串单词重构为英语句子

Question

我完全被难住了。问题是:假设你有一个像“thisisasentence”这样的字符串和一个函数 isWord()，如果它是一个英文单词则返回 true，我会卡在“this is a sent”

我怎样才能递归地返回并跟踪我每次的位置？

Answer 1

你需要backtracking ，使用递归很容易实现。关键观察是，您不需要跟踪在您准备返回解决方案的那一刻过去的位置。

当满足以下任一条件时，您的“拆分”有效:

• 字符串 w 为空(基本情况)，或者
• 您可以将非空 w 拆分为子字符串 p 和 s，这样 p+s=w，p是一个词，s可以拆分成一个句子(递归调用)。

实现可以在找到成功拆分时返回单词列表，或者在找不到时返回 null。基本情况将始终返回一个空列表；递归案例将在找到 p、s 拆分后导致 s 返回非空值，构造一个包含 p 的列表 作为递归调用返回列表的前缀。

递归的情况下会有一个循环，尝试所有可能的w前缀。为了加快速度，循环可以在到达长度等于字典中最长单词的前缀时终止。例如，如果最长的单词有 12 个字符，您知道尝试使用 13 个字符或更长的前缀不会导致匹配，因此您可以缩短枚举。