java - 检查一个字符串是否与其他两个字符串交错

Question

我遇到了问题解决方案的多个链接 - “如何检查一个字符串是否与其他两个字符串交错”

有两个解决方案对我来说特别有趣，但我对它们都有疑问。

FIRST我没有得到哈希部分，作者说“纯递归解决方案会导致超过时间限制。我们可以通过在访问集中缓存错误访问的解决方案来优化它。这将使许多重复的搜索路径短路”

SECOND我没有递归第 18 行的“其他条件”。如果条件 if(s2.charAt(0) != s3.charAt(0) && s1.charAt(0) != s3.charAt(0)) {

Answer 1

首先

这实际上是时空权衡(可以以增加内存使用为代价来减少计算时间)。为什么作者说纯递归解法慢(其实是指数时间复杂度)？它来自重复递归，因此，它一次又一次地计算相同的值。

那你能做什么？您可以存储已经计算出的值。下次您再次需要此值时，只需查找表格即可。这称为缓存，当值被缓存时，您可以像在 O(1) 时间复杂度中运行一样对待函数内的每个递归调用。核心思想是不要对相同的事情进行两次计算。

第二

在 s2.charAt(0) == s3.charAt(0) && s1.charAt(0) == s3.charAt(0) 的情况下。