1 回答

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);
}
}
應該總是可以解決像這樣的遞歸問題,但是如果證明它太難了,您可以作為替代方法,傳遞一個額外的對象變量(或數組),遞歸調用會將其結果添加到其中:就像一個逐漸成長為最終解決方案的收集器。不利的一面是,不讓函數產生副作用是違反最佳實踐的,其次,此函數的調用者必須已經準備了一個空對象并傳遞它以獲取結果。
最后,不要試圖將全局變量用于此類數據收集。如果這種“全局”變量實際上是閉包中的局部變量,那就更好了。但是,另一種選擇是首選。
添加回答
舉報