不理解这种在 2 个字符串之间查找子序列的迭代方法

Question

这是问题：

Write a function called isSubsequence which takes in two strings and checks whether the characters in the first string form a subsequence of the characters in the second string. In other words, the function should check whether the characters in the first string appear somewhere in the second string, without their order changing.

我有下面的解决方案，但有几个部分我不明白：

为什么需要：if (!str1) return true;
我也听不懂这行：if (i===str1.length) return true;

感谢任何解释，谢谢！

function isSubsequence(str1, str2) {
  var i = 0;
  var j = 0;
  if (!str1) return true;
  while (j < str2.length) {
    if (str2[j] === str1[i]) i++;
    if (i === str1.length) return true;
    j++;
  }
  return false;
}

Answer 1

if (!str1) return true;

当第一个字符串为空字符串时，此语句 return 成立。因为我们可以通过删除另一个字符串的所有字符来导出一个空字符串。这就是为什么空字符串是任何字符串的子序列。除非明确提到我们正在寻找 non-empty 子序列。 Ref

if (i===str1.length) return true;

当我们检查两个字符串的字符是否相等时，如果我们到达第一个字符串的末尾并且所有前面的字符都相等，我们可以说 str1 是 str2 的子序列。此时我们需要从函数中return，否则，你将无法在str1中找到另一个字符。你可以看下面的例子。

str1 = 'abc'.

str2 = 'abcdefg'.

i=0,j=0:

str1[i] = 'a'

str2[j] = 'a'

i=1,j=1:

str1[i] = 'b'

str2[j] = 'b'

i=2,j=2:

str1[i] = 'c'

str2[j] = 'c'

此时我们在 str1 的末尾。现在如果我们不 return 那么会发生什么？

i=3,j=3

str1[3] = 'garbage values'

str2[3] = 'd'

它们不匹配，所以我们不断增加 j 的值，但我们不会更新 i 的值。因为if (str2[j] === str1[i]) i++;。在那种情况下，我们将遍历 str2 长度，最后我们将 return false。这是一个错误的结果。

Answer 2

Why the need for: if (!str1) return true;

这是一个边界案例。它检查第一个字符串是否为空。有人会问：空字符串是否总是另一个字符串的子序列？答案是：是的。

可以使该语句看起来与另一个 if 语句相同：if (i === str1.length) return true;。那也行。它表明实际上它正在执行相同的测试，但是对于 i 为 0.

的情况

如果保证第二个字符串不为空，则实际上不需要此语句，因为在这种情况下，循环将进行第一次迭代，而另一个 if 语句的条件将为真，因此该函数仍然 return 为真。然而，如果 both 字符串都是空的，函数也应该 return 为真，如果你没有这个语句就不会发生这种情况。

I don't get this line either: if (i===str1.length) return true;

i代表你在str2中找到的str1的字符数（按顺序）。所以如果 i 等于第一个字符串的长度，那么你就知道你已经找到了 str1 的所有字符：所以继续循环是没有意义的，因为没有其他东西可以找到。因此，是时候以积极的结果退出该功能了。

备选

您可以使 loop-condition 包含此“退出”条件的否定，这样您就不再需要 if：

function isSubsequence(str1, str2) {
  let i = 0;
  // Continue as long as there are characters to compare...
  for (let j = 0; i < str1.length && j < str2.length; j++) {
    if (str2[j] === str1[i]) i++;
  }
  // Now return true if, and only when, all of str1 was found in str2
  return i === str1.length;
}

不理解这种在 2 个字符串之间查找子序列的迭代方法

don't understand this iterative approach to finding a subsequence between 2 strings

javascript

algorithm

pointers

sequence

备选