CODEWITHSUNDEEP
javascriptalgorithm
devdropper87
devdropper87

Reputation: 4207

runtime of checking an array of strings for palindromes

I wrote a function to find palindromes in an array of strings. at first I looped through the array and checked each item to see if it was a palindrome with a helper function which checks the word (by letter) at each index in the array -- this would be O(n^2) correct?

I then changed my approach to pop off the array (treat it like a stack) and then check if that one item is a palindrome, and do that throughout the array while array.length. This is O(n), correct?

'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

Upvotes: 2

Views: 105

Answers (2)

Salvador Dali
Salvador Dali

Reputation: 222771

It is still unclear what do you mean here by O(n) (remember that O(n) represents the growth of computation in respect to the length of the input). Here it is not clear with respect do you want to count.

If your n is the sum of lengths of all characters in an array of strings, than both of your algorithms is O(n). If you have n - the length of your string and m the number of your strings in array - you have O(nm).

Upvotes: 1

OneCricketeer
OneCricketeer

Reputation: 191874

Checking for a palindrome of a string of length m is O(m).

Simply looping over an array (or stack) of length n is O(n).

Doing both is only O(n^2) if the maximum string length is n. Otherwise, it's O(n*m)

Upvotes: 1

Related Questions