检查字符串数组中的回文的运行时

runtime of checking an array of strings for palindromes

本文关键字：回文 运行时 字符串 数组 检查      更新时间：2023-09-26

我编写了一个函数来查找字符串数组中的回文。起初，我循环遍历数组，检查每个项目，看看它是否是一个带有辅助函数的回文，该函数检查数组中每个索引处的单词（按字母）——这是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

这里所说的O(n)是什么意思还不清楚（请记住，O(n)表示相对于输入长度的计算增长）。这里不清楚你想数多少。

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

检查长度为m的字符串的回文是O(m)。

简单地在长度为n的数组（或堆栈）上循环就是O(n)。

如果最大字符串长度为n，则同时执行这两个操作仅为O(n^2)。否则，它是O(n*m)

相关文章：