使用 JavaScript 遞迴獲取字串的所有子字串

在給定的問題陳述中，我們的目標是藉助 Javascript 遞迴獲取字串的所有子字串。因此，在這裡我們將建立一個遞迴函式，該函式可以生成給定輸入字串的所有可能的子字串。

理解問題陳述

問題陳述要求我們建立一個遞迴函式，該函式可以藉助 Javascript 生成給定輸入字串的所有可能的子字串。子字串是輸入字串中任何連續的字元序列。例如：輸入字串“xy”，則可能的子字串為“x”、“y”和“xy”。

演算法

步驟 1 - 透過定義函式並向其中傳遞一個引數（即我們要查詢子字串的字串）來啟動程式。

步驟 2 - 定義一個數組來儲存子字串的結果陣列。並將其初始化為零值。

步驟 3 - 使用另一個遞迴函式，並向其中傳遞兩個引數作為起始索引和結束索引。

步驟 4 - 宣告一個基本情況並檢查結束索引是否等於字串長度的條件。如果相等，則返回。

步驟 5 - 使用一個遞迴情況，在其中我們將檢查起始索引是否大於結束索引，然後再次呼叫遞迴函式並將結束索引加 1。

步驟 6 - 否則，透過切片字串並將 startIndex 和 endIndex 傳遞給結果進行推送。並再次呼叫遞迴函式。

步驟 7 - 呼叫遞迴函式並返回結果。

演算法程式碼

// function to get the substrings for the given string
function getAllSubstrings(str) {
   let result = [];

   function recurse(startIndex, endIndex) {
      // Base case
      if (endIndex === str.length) {
         return;
      }

      // Recursive case
      if (startIndex > endIndex) {
         recurse(0, endIndex + 1);
      } else {
         result.push(str.slice(startIndex, endIndex + 1));
         recurse(startIndex + 1, endIndex);
      }
   }

   recurse(0, 0);
   return result;
}

const inputStr = "wxyz";
const subStr = getAllSubstrings(inputStr);
console.log(subStr);

複雜度

上述遞迴函式的時間複雜度為 O(n^2)，其中 n 是輸入字串的長度。因為該函式會生成給定輸入字串的所有可能的子字串。此外，我們在記憶體中包含 (n^2) 個子字串，因此程式碼具有 O(n^2) 的空間複雜度。

結論

在 Javascript 程式碼中，我們使用了遞迴策略來查詢給定字串的所有可能的子字串。透過使用巢狀函式，程式碼正在生成所有可能的字串。遞迴函式會使用不同的引數執行，直到沒有建立子字串。

更新於：2023 年 5 月 18 日

2K+ 閱讀量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告