5
\$\begingroup\$

I have written an algorithm intended to find prefixes and suffixes in arrays of strings.

I would like to get opinions/suggestions/reviews on the code I wrote (specially cases in which my code would fail), but also, I would like to know if this algorithm can be rewritten in a more optimal way since I will be running this code against lots of entries.

Finding preffixes

function findPrefix(strings){
    if(!strings || strings.length === 0){
        return null;   
    }

    var prefix = '',
        characters = strings[0].split(''),
        i, j;

    for(i = 0; i < characters.length; i++){
        var isPrefix = true,
            character = characters[i];

        for(j = 0; j < strings.length; j++) {
            var string = strings[j];

            isPrefix = isPrefix && 
                (string.length >= i + 1 && string[i] === character);
        }

        if(isPrefix) {
            prefix += character;
        } else {
            return prefix;
        }
    }
}

Finding suffixes

function reverse(string){
    return string.split('').reverse().join('');
}

function findSuffix(strings){
    if(!strings || strings.length === 0){
        return null;   
    }

    return reverse(findPrefix(strings.map(reverse)));
}

A running example can be found here: http://jsbin.com/razuta/2/edit (click JavaScript and console to see the results)

\$\endgroup\$
  • \$\begingroup\$ You can use String's charAt method instead of characters = strings[0].split(''); ... characters[i] \$\endgroup\$ – hindmost Oct 8 '14 at 19:09
  • \$\begingroup\$ Since this would make the code more readable I agree with you. Do you think there would also be performance improvements in this change? \$\endgroup\$ – Renato Gama Oct 8 '14 at 19:12
  • \$\begingroup\$ No, I don't think so since split is applied only once. \$\endgroup\$ – hindmost Oct 8 '14 at 19:19
  • 1
    \$\begingroup\$ KMP is one of easy and efficient algorithms \$\endgroup\$ – outoftime Oct 8 '14 at 19:22
  • 1
    \$\begingroup\$ @outoftime But KMP is about finding a string anywhere in another string. Here, we're anchored to the beginning of the string. \$\endgroup\$ – Flambino Oct 8 '14 at 19:31
7
\$\begingroup\$

As Martin R said, if all strings must match a common prefix, then that prefix is whatever the first and last string in a sorted array have in common.

The code in the SO answer isn't too pretty though. Here's my take (?):

function findPrefix(strings) {
  if(!strings.length) {
    return ""; // or null or undefined; your choice
  }

  var sorted = strings.slice(0).sort(), // copy the array before sorting!
      string1 = sorted[0],
      string2 = sorted[sorted.length-1],
      i = 0,
      l = Math.min(string1.length, string2.length);

  while(i < l && string1[i] === string2[i]) {
    i++;
  }

  return string1.slice(0, i);
}

Compared to the SO answer, the main point here (besides style and camelCased variables) is that the array is copied, and the copy is sorted. Otherwise, the same array object that was passed to the function will be sorted as a side-effect.

Compared to your code, I've skipped the strings-it-truth'y check at the very start. I prefer to assume that arguments are at least the correct type (i.e. an array) - otherwise it's the caller's problem.

As for your current code:

  • As mentioned in the comments, you can use string.charAt(i) or simply string[i] (though the latter is a more recent addition to JS) instead of splitting the string into an array.

  • Your inner loop starts at index 0 - but that's the same string you're already using as your characters array, so you already know that it's going to match.

  • The moment you hit a non-match, use break to skip the rest of the loop. My bad, you're already returning from the loop, which has the same effect.

As for finding suffixes, your current code seems fine to me if you use the "sort-and-compare" approach above for findPrefix. Otherwise, it'd probably be infinitesimally faster to write a separate findSuffix function that just has its loops reversed. The logic's the same, the indices just run backward.

While nothing beats the sort-and-compare approach (except a better one; see below), here's, just for fun, another way to to use all strings, unsorted, to find the prefix:

function findPrefix(strings) {
  function commonPrefix(a, b) {
    var i = 0,
        l = Math.min(a.length, b.length);

    while(i < l && a[i] === b[i]) {
      i++;
    }
    return a.slice(0, i);
  }

  return strings.reduce(function (prefix, string) {
    // if prefix is empty or matches the string,
    // then just return the prefix immediately
    if(string.indexOf(prefix) === 0) {
      return prefix;
    }

    // otherwise, find the intersection between
    // prefix and the string
    return commonPrefix(prefix, string);
  });
}

Update: As MatinR pointed out in the comments, sort may be a drag on performance, and besides it isn't necessary, as you only need what would be the first and last string in a sorted array. These strings can alternative be found like so:

function extremes(strings) {
  // grab two strings to use as our initial guesses
  var initial = {
    largest: strings[0],
    smallest: strings[strings.length-1]
  };

  // loop through to find the extremes
  return strings.reduce(function (memo, string) {
    // slightly funky syntax, but it's short.
    (memo.largest > string) || (memo.largest = string);
    (memo.smallest < string) || (memo.smallest = string);
    return memo;
  }, initial);
}

The two strings in the returned object may then be used to determine the shared prefix (if any). The entire thing can also be built into findPrefixes, of course, rather than be a separate function as shown below:

function findPrefix(strings) {
  if(!strings.length) {
    return ""; // or null or undefined; your choice
  }

  var string1 = strings[0],
      string2 = strings[strings.length-1],
      i, l;

  // note: a regular for-loop is faster than forEach
  // I'm using forEach because it's prettier
  strings.forEach(function (string) {
    (string1 < string) || (string1 = string);
    (string2 > string) || (string2 = string);
  });

  i = 0;
  l = Math.min(string1.length, string2.length);
  while(i < l && string1[i] === string2[i]) {
    i++;
  }

  return string1.slice(0, i);
}
\$\endgroup\$
  • \$\begingroup\$ I am not fluent in JavaScript, that's why I just pointed to the basic idea :) Note that it is not strictly necessary to sort the array, you only need the "smallest" and "largest" string. \$\endgroup\$ – Martin R Oct 8 '14 at 20:18
  • 1
    \$\begingroup\$ This is a good approach, but I would definitely profile it with the real-live data. As sorting is quite expensive, and will always happen, it might take longer than the approach the OP has (which might return quite early, depending on the data). \$\endgroup\$ – tim Oct 8 '14 at 20:23
  • \$\begingroup\$ @MartinR Note sure I follow; if you mean smallest/largest in terms of length, then ["abc", "xyz", "ab"] could mistakenly return "ab" as the prefix. You'd still need sorting, as far as I can tell. \$\endgroup\$ – Flambino Oct 8 '14 at 20:25
  • 1
    \$\begingroup\$ @Flambino: I meant smallest/largest in terms of (lexicographic?) ordering, i.e. in terms of the comparison function used by sort() (the algorithm only uses the first and the last element of the sorted array). \$\endgroup\$ – Martin R Oct 8 '14 at 20:27
  • \$\begingroup\$ @MartinR Right, I think I see what you mean. I was thinking that lexicographically determining largest/smallest would automatically imply sorting, but of course it doesn't. \$\endgroup\$ – Flambino Oct 8 '14 at 20:31
5
\$\begingroup\$

(From https://stackoverflow.com/a/1917041/1187415 and the following comments:)

You can determine the "smallest" and "largest" string (in terms of the lexicographic ordering of strings) in the array first and determine the longest common prefix of these two. This is necessarily a prefix of all other strings in the array.

\$\endgroup\$
3
\$\begingroup\$

Performance

isPrefix = isPrefix && exp

As false && bool is always false, you are doing some unnecessary loops in your program. The quickest way to fix it would be to just add if (!isPrefix) { break; } after assigning isPrefix in the inner for loop. And then the assignment to isPrefix could just be isPrefix = string.length >= i + 1 && string[i] === character;.

But you could also get rid of the isPrefix var altogether and to it like this:

for(var i = 0; i < characters.length; i++){
        character = characters[i];

    for(var j = 0; j < strings.length; j++) {
        var string = strings[j];
        var isPrefix = string.length >= i + 1 && string[i] === character;

        if (!isPrefix) {
            return prefix;
        }
    }
    prefix += character;
}

General Review

Duplicate Code

You have this check: if(!strings || strings.length === 0) twice. You could extract it to a function.

Variable Declaration

It is often best to define variables as close to where they are used as possible, so it might be better to declare i and j inside the loop.

\$\endgroup\$
  • \$\begingroup\$ The smallest scope in JS is a function. Loops do not have their own scope. So declaring i and j inside the loop still declares them at the function level. Hence the recommendation (pretty much followed by OP) to declare variables at the top of the function in which they appear. \$\endgroup\$ – Flambino Oct 8 '14 at 19:34
  • \$\begingroup\$ @Flambino maybe scope wasn't the correct word, as they indeed live outside the loop even when declared inside. But I think that declaring variables as close to the place where they are used as possible is still best practice and that declaring all variables at the top of a method is quite outdated (see for example here or here). \$\endgroup\$ – tim Oct 8 '14 at 19:39
  • 1
    \$\begingroup\$ Recommendations are recommendations; my main point was just that "scope" isn't quite right. I personally like to declare variables at the top (though I break that rull all the time, too), but you're of course free to recommend something else. But calling it "scope" can get confusing since other language do have scoped loops - but that's not why you'd declare vars "locally" in JS. \$\endgroup\$ – Flambino Oct 8 '14 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.