这个回文算法的时间和空间复杂度？

Question

有人能告诉我这个算法的时间和空间复杂度吗？基本上，函数接受一个字符串，如果它是回文(与向前相同)，则该函数必须返回true；如果不是，则返回false。

我认为这是O(n)，但如果我错了，请纠正我。

function isPalindrome(string) {
    var reversing = string.split("").reverse().join("")
    return string === reversing
}

Answer 1

您的函数的时间和空间复杂性为O(string.length)，因为它构造了一个字符数组，然后构造了一个新字符串，该字符串的字符顺序相反，长度与原始字符串相同。比较这些字符串具有相同的时间复杂度。

然而，请注意，这对单个单词有效，但对完整的短语不起作用:可以用相同的字母在两个方向上阅读的短语，但不一定是相同的间距，也是回文。

以下是另一种版本：

function isPalindrome(string) {
    string = string.replace(/ /g, "");
    var reverse = string.split("").reverse().join("");
    return string === reverse;
}

该函数具有与O(string.length).相同的时间和空间复杂度。