如何最小化执行时间？

Question

我正在检查给定的字符串是否为回文，但是执行时间太长了。

我的代码如下：

function checkPalindrome(inputString) {
  for (let i = 0; i < (inputString.length - 1) / 2; i++) {
    const a = inputString[i];
    const b = inputString.split("").reverse().join("")[i];
    if (a !== b) {
      return false;
    }
    continue;
  }
  return true;
}
const palindrome = checkPalindrome("abba");
console.log(palindrome);

如何优化代码以减少其执行时间？

Answer 1

您可以使用简单的 for 循环进行检查

function checkPalindrome(inputString) {
    const len = inputString.length;
    for (let i = 0; i < len / 2; i++) {
        if (inputString[i] !== inputString[len - 1 - i])
            return 'not a palindrome';
    }
    return 'palindrome';
}

console.log(checkPalindrome('madam'))

Answer 2

不要重复自己！您在每次迭代中拆分和反转字符串。

function checkPalindrome(inputString) {
  const reversed = inputString.split("").reverse()
  for (let i = 0; i < (inputString.length - 1) / 2; i++) {
    const a = inputString[i];
    const b = reversed[i]
    if (a !== b) {
      return false;
    }
    continue; /// pointless also - you're already at the end of the loop
  }
  return true;
}


console.log(checkPalindrome("sir"))
console.log(checkPalindrome("madam"))

这是最重要的一点，您还可以进行其他微优化，例如不必每次都评估循环控制，但除非您的输入很大，否则效果会很小。

Answer 3

更好：

function palindrome(str) {
  var re = /[\W_]/g;
  // convert to lower case and remove spaces
  var lower = str.toLowerCase().replace(re, '');
  // reverse the string
  var reverse = lower.split('').reverse().join(''); 
  // check if reversed and actual string is same
  return reverse === lower;
}

console.log(palindrome("sir"))
console.log(palindrome("madam"))

Answer 4

为什么要迭代每个字母，什么时候可以使用数组方法反转它？

function checkPalindrome(inputString) {
  return inputString === inputString.split("").reverse().join("");
}

let palindrome = checkPalindrome("abba");
console.log(palindrome);

palindrome = checkPalindrome("random");
console.log(palindrome);

palindrome = checkPalindrome("abba isi abba");
console.log(palindrome);

Answer 5

这里有一个有点高效的recursive解决方案

function checkPalindrome(inputString) {
    const n = inputString.length
    if(n == 0 || n == 1)
        return true;
    else{
        if(inputString[0] != inputString[n-1]){
            return false;
        }
    }
    const t = inputString.slice(1, n-1)
    return checkPalindrome(t)
    }

console.log(checkPalindrome("abbca"))

或更高效

    function checkPalindrome(inputString) {
        return (inputString.split("").reverse()).join('') === inputString
    }

console.log(checkPalindrome("abba"))

如何最小化执行时间？

How to minimize the execution time?

javascript

execution-time