我正在尝试递归地解决一个通用回文问题。但是，我的算法似乎只计算第一个递归调用，而不是第二个，第二个应该检查字符串中的所有字符。显然，我的算法中有一个逻辑错误，但我不能发现它。有人能给我建议吗？请看下面的代码。
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"));
1条答案
按热度按时间62lalag41#
有几个问题：
1.您的
if...else将始终导致return，因此永远不会执行带有递归调用的语句。请注意，
else if后面的条件在求值时始终为true，因为它是前面的if语句中求值的条件的否定。更重要的是，当前面的
if条件为真时，您 * 不 * 希望返回，因为还没有验证剩余的（内部）字符是否匹配。这仍然需要通过递归调用来验证，所以这里不是执行return的地方。只需删除那个if块，当字符不同时只删除return。因此替换为：
佐甫：
1.第一次递归调用传递的参数与当前执行的函数get * 相同 *--这将导致无限递归。递归调用必须总是使问题变小。在这种情况下，实际上不需要进行两次递归调用，并且您应该删除第一次调用。
因此替换为：
与：
1.基本情况有一个条件，即执行
return时不返回布尔值。函数应始终返回布尔值。在本例中，它应为true，因为这意味着所有字符对都已比较，并且没有保留单中间字符（字符串的大小是偶数）。因此，您可以将这种情况与前面的基本情况结合起来。实际上，当totalChars为0时，基本情况条件也会起作用。因此可以忽略第一个if。所以改变一下：
与：