JavaScript 中匹配子字符串的计数

准确计算给定字符串中匹配子字符串的能力是 JavaScript 编程中一项关键技能，因为它使开发人员能够高效地分析和操作文本数据。本文深入探讨字符串操作领域，探讨了在 JavaScript 中计算匹配子字符串的复杂性，并采用了一系列鲜为人知的技术。通过阐明底层逻辑并采用这些非常规方法，开发人员可以更深入地了解如何有效地统计特定子字符串的出现次数，从而能够从文本数据中提取有意义的见解。加入我们这次富有启发意义的旅程，让我们一起释放 JavaScript 强大功能的潜力，并扩展我们稀有词汇的范围，以掌握计算匹配子字符串的艺术。

问题陈述

我们需要一个 JavaScript 函数来计算给定字符串中的子序列，该函数接收名为“str”的字符串输入和名为“arr”的字符串数组输入。目标是检查“arr”中的每个元素并确定作为“str”的子序列的字符串数量。“子序列”是指可以通过从原始字符串中删除字符而形成的字符串，同时保持剩余字符的相对顺序。该函数应仔细比较“arr”中的每个元素与“str”，并确定是否可以通过从“str”中删除字符来构造它。然后，它将返回一个整数，表示在“str”中找到的合格子序列的数量。

示例输入 -

str = 'abracadabra';
arr = ['a', 'bra', 'cad', 'dab'];

示例输出 -

Output =4;

输出解释 -

在给定的输入中，字符串“str”是“abracadabra”，数组“arr”包含['a', 'bra', 'cad', 'dab']。

分析“arr”的每个元素，我们发现'a'、'bra'、'cad'和'dab'都是“str”的子序列。因此，子序列的数量为 4，这是预期的输出。

方法

在本文中，我们将了解几种在 JavaScript 中解决上述问题陈述的不同方法 -

  • 蛮力法

  • 双指针法

Learn JavaScript in-depth with real-world projects through our JavaScript certification course. Enroll and become a certified expert to boost your career.

方法 1：蛮力法

计算有效子序列的蛮力法涉及生成字符串的所有可能子序列并检查它们是否存在于数组中。我们迭代每个字符串，递归地或使用位操作生成子序列，并将它们与数组元素进行比较。对于每个匹配，计数器都会递增，从而给出总数。对于较大的输入，此方法在计算上代价很高，因此动态规划等替代算法提供了更优化的解决方案。

示例

代码实现了一个递归算法，用于计算给定字符串 (str) 在字符串数组 (arr) 中的子序列数量。countSubsequences 函数初始化一个计数变量来跟踪有效的子序列。generateSubsequences 函数通过迭代输入字符串并检查每个子序列是否存在于数组中来生成所有可能的子序列。进行递归调用以探索包含或排除字符的不同可能性。主函数调用从字符串的开头开始生成子序列。计数变量作为最终结果返回。一个示例用法演示了该函数与示例字符串和字符串数组的用法。结果被存储并打印到控制台。

Open Compiler
function countSubsequences(str, arr) {
   let count = 0;
 
   // Generate all possible subsequences of the input string
   function generateSubsequences(sub, index) {
      if (index === str.length) {
         // Check if the subsequence exists in the array
         if (arr.includes(sub)) {
            count++;
         }
         return;
      }
 
      // Include the current character in the subsequence
      generateSubsequences(sub + str[index], index + 1);
 
      // Exclude the current character from the subsequence
      generateSubsequences(sub, index + 1);
   }
 
   // Start generating subsequences from the beginning of the string
   generateSubsequences("", 0);
 
   return count;
}
 
// Example usage:
const str = "abcde";
const arr = ["a", "ab", "bd", "abc", "acde", "eab"];
const result = countSubsequences(str, arr);
console.log(result);

输出

以下是控制台输出 -

5

方法 2：双指针法

该算法遍历数组中的每个字符串，并使用两个指针，一个用于给定字符串，另一个用于当前正在检查的字符串。这些指针最初位于其对应字符串的第一个字符处，然后向前推进，直到它们遇到任一字符串的末尾。每次确定有效子序列时，数值指示器都会递增。最终，该算法提供指示器的数值作为最终结果。

示例

函数 countValidSubsequences 以字符串数组 (arr) 和目标字符串 (target) 作为参数。它迭代 arr 中的每个字符串，并使用嵌套循环将其字符与 target 中的字符进行比较。如果字符匹配，则递增索引；如果不匹配，则仅递增 target 的索引。如果整个字符串是有效的子序列，则递增计数。在迭代 arr 中的所有字符串之后，函数返回最终计数。

Open Compiler
function countValidSubsequences(arr, target) {
   let count = 0;
 
   for (let i = 0; i < arr.length; i++) {
      const current = arr[i];
      let j = 0;
      let k = 0;
 
      while (j < current.length && k < target.length) {
         if (current[j] === target[k]) {
            j++;
            k++;
         } else {
            k++;
         }
      }
 
      if (j === current.length) {
         count++;
      }
   }
 
   return count;
}
 
// Example usage: 
const str = "abcde"; 
const arr = ["a", "ab", "bd", "abc", "acde", "eab"]; 
const result = countValidSubsequences(arr, str); 
console.log(result);

输出

以下是控制台输出 -

5

结论

总之，对在 JavaScript 中计算匹配子字符串的探索发现了很多巧妙的技术，可以用来高效地完成这项任务。通过使用各种算法并利用该语言很少使用的功能，程序员可以设计出优雅且资源丰富的解决方案。必须承认，子字符串匹配的复杂性需要仔细考虑边缘情况和潜在的性能影响。然而，有了这些新的见解，开发人员可以超越传统方法，并充分利用 JavaScript 的潜力来巧妙地枚举和操作子字符串。总之，本文分享的深奥知识使程序员能够提升其编码能力，并在 JavaScript 中开启子字符串计数的新维度。

更新于：2023年8月4日

112 次查看

启动您的 职业生涯

通过完成课程获得认证

开始
广告