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 中解決上述問題陳述的不同方法 -

• 蠻力法

• 雙指標法

方法 1：蠻力法

計算有效子序列的蠻力法涉及生成字串的所有可能子序列並檢查它們是否存在於陣列中。我們迭代每個字串，遞迴地或使用位操作生成子序列，並將它們與陣列元素進行比較。對於每個匹配，計數器都會遞增，從而給出總數。對於較大的輸入，此方法在計算上代價很高，因此動態規劃等替代演算法提供了更最佳化的解決方案。

示例

程式碼實現了一個遞迴演算法，用於計算給定字串 (str) 在字串陣列 (arr) 中的子序列數量。countSubsequences 函式初始化一個計數變數來跟蹤有效的子序列。generateSubsequences 函式透過迭代輸入字串並檢查每個子序列是否存在於陣列中來生成所有可能的子序列。進行遞迴呼叫以探索包含或排除字元的不同可能性。主函式呼叫從字串的開頭開始生成子序列。計數變數作為最終結果返回。一個示例用法演示了該函式與示例字串和字串陣列的用法。結果被儲存並列印到控制檯。

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 中的所有字串之後，函式返回最終計數。

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 中開啟子字串計數的新維度。