Compare a list of strings: Faster Way to solve?

Compare a list of strings: Faster Way to solve?
0

#1

Tell us what’s happening:
Wondering if people have got some faster ways to implement azSorted. I used a method of comparing each char in adjacent elements. Find the shortest length out of the 2 and compare up to that index the charCodes. There are then 4 cases to cover the outcomes and edge case. This seems inefficient like bubble sort.

I know there are faster ways can people shed some light on possible solutions that still cover all edge cases?

Your code so far


function allEqual (arr) {
  if (arr.length === 0){
    return true;
  }
  let resArr = [];
  for (let i = 0; i < arr.length; i++){
    let tally = 0;
    for (let j = 0; j < arr[i].length; j++){
      tally += arr[i].charCodeAt(j);
    }
    resArr.push(tally);
  }
  let total = resArr.reduce((acc,curr)=>acc+curr);
  if (total%resArr[0] === 0){
    return true;
  }
  return false;
}

function azSorted (arr) {
  // Good luck!
  if (arr.length === 0){
    return true;
  }
  for (let i = 0; i < arr.length-1; i++){
    let shortestLen = 0;
    let elem1 = arr[i];
    let elem2 = arr[i+1];
    if (elem1.length <= elem2.length){
      shortestLen = elem1.length;
    }else{
      shortestLen = elem2.length;
    }
    for (let j = 0; j < shortestLen; j++){
      if(elem1.charCodeAt(j) === elem2.charCodeAt(j) && j === shortestLen-1){
        return false;
      }else if (elem1.charCodeAt(j) === elem2.charCodeAt(j)){
        continue;
      }else if (elem1.charCodeAt(j) < elem2.charCodeAt(j)){
        break;
      }else{
        return false;
      }
    }
  }
  return true;
}

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.99 Safari/537.36.

Link to the challenge:
https://learn.freecodecamp.org/coding-interview-prep/rosetta-code/compare-a-list-of-strings


#2

Suppose

  • the number of element in an array is n
  • all string has the same length m

To check for lexical order,

  • you must compare elements sequentially by pairs, which takes n-1 times .
    e.g) For 3 element array ["AA", "AB", "AC"] compare (AA, AB), (AB, AC), which takes 2 times.
  • for each pair, compare each string by position, which takes m times.
    e.g) For (AB, CD) pair, compare (A, C) and (B, D)

So, roughly speaking this will take n*m times. Doing m comparisons for n items.

AFAIK, there is no faster way to do this given that both length of string and size of array is arbitrary; just like you must flip each card to know which one is the greatest.

Lexical comparison for strings is already implemented in JS, so checking if all of the elements are lexically sorted can be simpler.

function azSorted (arr) {
  for (let i = 1; i < arr.length; ++i) {
    if (arr[i - 1] >= arr[i]) {
      return false
    }
  }
  return true;
}

I’ve done some rough benchmark with worst case input with 1000 repeats and yours was 4.35 times slower. So, both simpler and faster way to do this is just use built-in language feature.

Possible reasons for yours being slower is the length check to get shorter length. You don’t really have to do this beforehand.

This article describes some cases where the running time can be improved.


#3

Wow thanks for the breakdown. Yep realised since i posted, JS has in built comparison for strings. Way easier and faster. Always interesting the computer science of relatively simple problems like this.