此javascript递归解决方案中，用于检查字符串是否为回文符的功能是什么？]

Question

我发现了一些非常有用的解决方案，可以编写Javascript函数来递归检查字符串是否是回文here。我想知道以下解决方案的时间和空间复杂度是多少。您能解释一下每一行对大O的贡献吗？

function isPalindrome(string) {
    if (string.length < 2) return true;
    if (string[0] === string[string.length - 1]) {
        return isPalindrome(string.slice(1, string.length - 1))
        }
    return false;
}

我发现了一些非常有用的解决方案，可以编写Javascript函数来递归检查此处的字符串是否是回文。我想知道...

Answer 1

起初，您的函数似乎是O（n），因为您递归调用了n / 2次。但是，在每个呼叫中​​，您还使用string.slice，其复杂度为O（n）。因此，您的函数实际上是O（n ^ 2）

Answer 2

您递归地调用该函数n / 2次，其中n是字符串的长度，因为您在每次迭代时都删除了字符串的第一个和最后一个条目。