亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

遞歸:當可能有多個子路徑時,跟蹤所有遞歸路徑中的變量

遞歸:當可能有多個子路徑時,跟蹤所有遞歸路徑中的變量

烙印99 2021-07-07 02:10:01
我試圖計算模式作為字符串的子序列出現的次數,并保留匹配發生的索引。使用遞歸調用很容易計數。function count(str, pattern, strInd, patternInd) {    if (patternInd === 0) {      return 1;    }    if (strInd === 0) {      return 0;    }    if (str.charAt(strInd - 1) === pattern.charAt(patternInd - 1)) {      const count1 = count(str, pattern, strInd - 1, patternInd - 1);      const count2 = count(str, pattern, strInd - 1, patternInd);      return count1 + count2;    } else {      return count(str, pattern, strInd - 1, patternInd);    }  }為了保持索引,我的邏輯是當模式字符與字符串字符匹配時,將 str 的當前索引推送到遞歸調用中的“本地索引數組”,并且一旦模式完成,將“本地索引”推送到“全局索引”并為下一個遞歸路徑重置“本地索引”。重置本地索引是我面臨的問題:function count(str, pattern, strInd, patternInd) {    if (patternInd === 0) {      // when this path ends, add to list the indices found on this path      globalIndices.push(localIndices);      // reset the local indices      localIndices = [];      console.log("found");      return 1;    }    if (strInd === 0) {      return 0;    }    if (str.charAt(strInd - 1) === pattern.charAt(patternInd - 1)) {      localIndices.push(strInd);      const count1 = count(str, pattern, strInd - 1, patternInd - 1);      const count2 = count(str, pattern, strInd - 1, patternInd);      return count1 + count2;    } else {      return count(str, pattern, strInd - 1, patternInd);    }  }這樣它在每次分叉后都會丟失之前的路徑信息,因為一旦匹配的子路徑被消耗,它就會從 localIndices 中刪除,并且 localIndices 在分叉發生后開始跟蹤匹配。因此,例如,str 是“abab”,模式是“ab”,那么我想要 globalIndices = [[4,3], [4,1], [2,1]] 但我會得到 [[4, 3],[1],[2,1]]我想將“本地索引”重置為之前的分叉。我是在朝著正確的方向前進,還是這些問題需要完全不同的實現?
查看完整描述

1 回答

?
jeck貓

TA貢獻1909條經驗 獲得超7個贊

首先,當您收集索引時,您不需要保留計數,因為最終數組的長度將是計數:每個數組元素將對應一個匹配項,并且是相關索引的列表。


您可以在回溯時使函數的返回值與(部分)匹配的數組匹配并使用額外的索引擴展每個數組(用于在匹配中使用該字符時):


function count(str, pattern, strInd = str.length, patternInd = pattern.length) {

    if (patternInd === 0) {

        return [[]]; // A match. Provide an array with an empty array for that match

    }


    if (strInd === 0) {

        return []; // No match. Provide empty array.

    }


    if (str.charAt(strInd - 1) === pattern.charAt(patternInd - 1)) {

        const matches1 = count(str, pattern, strInd - 1, patternInd - 1);

        const matches2 = count(str, pattern, strInd - 1, patternInd);

        // For the first case, add the current string index to the partial matches:

        return [...matches1.map(indices => [...indices, strInd-1]), ...matches2];

    } else {

        return count(str, pattern, strInd - 1, patternInd);

    }

}


console.log(count("abab", "ab")); 

請注意,索引是從零開始的,因此它們比您提到的預期輸出少一。此外,索引從左到右排序,這似乎更有用。


大概的概念

通常,您最好避免使用全局變量并盡可能多地使用遞歸函數的返回值。你從中得到的只會涉及遞歸調用訪問的“子樹”。在上述情況下,該子樹是字符串和模式的較短版本。遞歸函數返回的內容應該與傳遞的參數一致(應該是那些參數的“解決方案”)。


返回值可能很復雜:當您需要返回多個“一件事”時,您可以將不同的部分放在一個對象或數組中并返回。然后調用者可以再次將其解包到各個部分。例如,如果我們還要在上面的代碼中返回計數,我們會這樣做:


function count(str, pattern, strInd = str.length, patternInd = pattern.length) {

    if (patternInd === 0) {

        return { count: 1, matches: [[]] };

    }


    if (strInd === 0) {

        return { count: 0, matches: [] };

    }


    if (str.charAt(strInd - 1) === pattern.charAt(patternInd - 1)) {

        const { count: count1, matches: matches1 }  = 

             count(str, pattern, strInd - 1, patternInd - 1);

        const { count: count2, matches: matches2 } = 

             count(str, pattern, strInd - 1, patternInd);

        // For the first case, add the current string index to the partial matches:

        return {

            count: count1 + count2,

            matches: [...matches1.map(indices => [...indices, strInd-1]), ...matches2]

        };

    } else {

        return count(str, pattern, strInd - 1, patternInd);

    }

}

應該總是可以解決像這樣的遞歸問題,但是如果證明它太難了,您可以作為替代方法,傳遞一個額外的對象變量(或數組),遞歸調用會將其結果添加到其中:就像一個逐漸成長為最終解決方案的收集器。不利的一面是,不讓函數產生副作用是違反最佳實踐的,其次,此函數的調用者必須已經準備了一個空對象并傳遞它以獲取結果。


最后,不要試圖將全局變量用于此類數據收集。如果這種“全局”變量實際上是閉包中的局部變量,那就更好了。但是,另一種選擇是首選。


查看完整回答
反對 回復 2021-07-08
  • 1 回答
  • 0 關注
  • 237 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號