javascript - 检查字符串数组是否有回文的运行时

Question

我编写了一个函数来在字符串数组中查找回文。首先，我循环遍历数组并检查每个项目，看看它是否是带有辅助函数的回文，该函数检查数组中每个索引处的单词(按字母)——这将是 O(n^2) 正确吗？

然后我改变了弹出数组的方法(将其视为堆栈)，然后检查该一项是否是回文，并在 array.length 时在整个数组中执行此操作。这是 O(n)，对吗？

'use strict';

function isTextPalindrome(text) {
//this ignores anything other than letters
  text = text.replace(/[^a-zA-Z]/g, '').toLowerCase();

  // console.log(text);

  if (!text) {
    return "There must be text as an input!";
  }

  var left = 0;
  var right = text.length - 1;

  while (left < right) {
    if (text[left++] !== text[right--]) {
      return false;
    }
  }
  return true;
}

// console.log(isTextPalindrome('race car'));

function palindromesInArray(arr) {
  var popped;
  var count = 0;
  //treat the array as a stack. don't loop through, just pop off one at a time to avoid extra run time cost.  
  while (popped = arr.pop()) {
    if (typeof (popped) !== 'string') {
      return "Only works on strings";
    }
    if (isTextPalindrome(popped)) {
      count++;
    }
  }

  // for (let i = 0; i < arr.length; i++) {
  //   if (typeof (arr[i]) !== 'string') {
  //     return "Only works on strings";
  //   }
  //   if (isTextPalindrome(arr[i])) {
  //     count++;
  //   }
  // }
 return count;
}



console.log(palindromesInArray(['mom', 'race car', 'dad', 'abba', 'redivider', 'noon', 'civic', 'level', 'blah'])) // returns 8
console.log(palindromesInArray(['mom', 'race car', 'dad', 'blah'])); // returns 3

Answer 1

目前还不清楚 O(n) 的含义(请记住，O(n) 表示计算量相对于输入)。这里不清楚尊重你要不要算。

如果您的 n 是字符串数组中所有字符的长度之和，那么您的两种算法都是 O(n)。如果您有 n - 字符串的长度和 m 数组中字符串的数量 - 您就有 O(nm)。