遞回回圈遍歷字串中的字符以解決回文問題的問題-有解無憂

我試圖遞回地解決一個通用的回文問題。但是，我的演算法似乎只評估第一個遞回呼叫，而不是第二個，后者應該檢查字串中的所有字符。我的演算法中顯然存在邏輯錯誤，但我無法發現它。誰能建議？請參閱下面的代碼。

function isPalindrome(totalChars: number, lastIdx: number, str: string): boolean | undefined {
    console.log(`lastIdx: ${lastIdx}; char: ${str[lastIdx]}`);

    // const curIdx = lastIdx;
    let highIdx = lastIdx;
    const lowIdx = totalChars-1 - highIdx;

    // Base Case: 
    if(totalChars === 0) return true;
    if (lowIdx === highIdx) return true;
    if (lowIdx > highIdx) {
        console.log(`Endpoint reached; STR: ${str}; LOW: ${str[lowIdx]}; high: ${str[highIdx]}`);
        return;
    }

    if(str[lowIdx] === str[highIdx]) {
        console.log(`Loop through idx; STR: ${str}; LOW: ${str[lowIdx]}; high: ${str[highIdx]}`);
        return true;
    }
    else if(str[lowIdx] !== str[highIdx]) return false;


    // Recursive Case:
    return isPalindrome(totalChars, highIdx, str) && isPalindrome(totalChars, highIdx-1, str);
}


// console.log("a is Palindrome: "   isPalindrome("a".length, "a".length-1, "a"));
// console.log("motor is Palindrome: "   isPalindrome("motor".length, "motor".length-1,"motor"));
console.log("rotor is Palindrome: "   isPalindrome("rotor".length, "rotor".length-1,"rotor"));

uj5u.com熱心網友回復：

有幾個問題：

你if...else將始終導致 a return，因此永遠不會執行帶有遞回呼叫的陳述句。

請注意，后面的條件在else if被評估時將始終為真，因為它是對先前if陳述句中評估的條件的否定。

更重要的是，當前面的if條件為真時，您不想回傳，因為尚未驗證剩余（內部）字符是否匹配。這仍然需要通過遞回呼叫來驗證，所以這里不是執行return. 只需洗掉該if塊，并且僅return當字符不同時。

所以替換這個：
```
    if(str[lowIdx] === str[highIdx]) 
    {
        return true;
    }
    else if(str[lowIdx] !== str[highIdx]) return false;
```
只有：
```
    if(str[lowIdx] !== str[highIdx]) return false;
```
第一次遞回呼叫傳遞的引數與函式當前執行得到的引數相同——這將導致無限遞回。遞回呼叫必須始終使問題變小。在這種情況下，實際上沒有必要進行兩次遞回呼叫，您應該洗掉第一個。

所以替換這個：
```
return isPalindrome(totalChars, highIdx, str) && isPalindrome(totalChars, highIdx-1, str);
```
和：
```
return isPalindrome(totalChars, highIdx-1, str);
```
基本情況有一個條件，在return沒有布爾回傳值的情況下執行。該函式應始終回傳一個布林值。在這種情況下，它應該是true，因為這意味著所有字符對都進行了比較，并且沒有剩余的單個中間字符（字串的大小是偶數）。因此，您可以將此案例與之前的基本案例結合起來。事實上，該基本情況條件在totalChars為零時也適用，因此您可以先省略它if。

所以改變這個：
```
if (totalChars === 0) return true;
if (lowIdx === highIdx) return true;
if (lowIdx > highIdx) {
    return;
}
```
和：
```
if (lowIdx >= highIdx) return true;
```

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/537109.html

標籤：javascript打字稿算法递归回文

上一篇：如何洗掉Javascript物件中的物件（元素）？

下一篇：計算串列串列中的元素并將答案作為Prolog中的串列輸出