Find the smallest distance between any two given words in a string

Question

The task:

Find an efficient algorithm to find the smallest distance (measured in number of words) between any two given words in a string.

For example, given words "hello", and "world" and a text content of "dog cat hello cat dog dog hello cat world", return 1 because there's only one word "cat" in between the two words.

const s = "dog cat hello cat dog dog hello cat world";

My imperative solution:

function smallestWordDistance2({str, word1, word2}) {
  if (!str.match(word1) || !str.match(word2)) { return 0; }

  const strArr = str.split(" ");
  let iStart, iEnd, min;
  let count = 0;
  for (let x in strArr) {
    if (!iStart) {
      if (strArr[x] === word1) {
        iStart = word1;
        iEnd = word2;
      } else if(strArr[x] === word2) {
        iStart = word2;
        iEnd = word1;
      }
    } else {
      count++;
      if (strArr[x] === iStart) {
        count = 0;
      } else if (strArr[x] === iEnd) {
        if (count === 1) { return 0; }
        if (!min || min > count) {
          min = count;
        }
        [iStart, iEnd] = [iEnd, iStart];
        count = 0;
      }
    }
  }
  return min - 1;
}
console.log(smallestWordDistance2({str:s, word1:"hello", word2:"world"}));

My "functional" solution:

const smallestWordDistance3 = ({str, word1, word2} )=> {
  if (!str.match(word1) || !str.match(word2)) { return 0; }

  const strArr = str.split(" ");
  return strArr.reduce((acc, x, i) => {
    if (!acc.iStart) {
      if (x === word1) {
        acc.iStart = word1;
        acc.iEnd = word2;
      } else if(x === word2) {
        acc.iStart = word2;
        acc.iEnd = word1;
      }
    } else {
      acc.count++;
      if (x === acc.iStart) {
        acc.count = 0;
      } else if (x === acc.iEnd) {
        if (!acc.min || acc.min > acc.count) {
          acc.min = acc.count;
        }
        [acc.iStart, acc.iEnd] = [acc.iEnd, acc.iStart];
        acc.count = 0;
      }
    }
    return acc;

  }, {iStart: null, iEnd: null, count: 0, min: null}).min - 1;
};

console.log(smallestWordDistance3({str:s, word1:"hello", word2:"world"}));

At first I thought this was a good task for a regex solution, but the following code is the best I could do. It works with the given sample string. However a slight variance in the given string would make the code unusable, because it doesn't take into consideration that word1 and word2 can be swapped (the following code would return 2 instead of 1):

const s = "dog cat hello cat dog dog hello cat dog world dog hello";

const smallestWordDistance = ({str, word1, word2} )=> {
  if (!str.match(word1) || !str.match(word2)) { return 0; }
  const reg = new RegExp(`.*\\b${word1}\\s+(.*?)\\s+${word2}\\b`);
  const match = str.match(reg);
  return match ? match[1].split(" ").length : 0;
};

console.log(smallestWordDistance({str:s, word1:"hello", word2:"world"}));

I'm now not so sure anymore whether regex is the right approach. But if anyone got a good regex (JS flavor) solution, then I'd be very much interested.

Answer 1

After staring at your code for some time,

• You are using Hungarian notation, that is not a JavaScript practice
  • Related to that, strArr probably should have been arrStr if the code was consistent
• It seems odd that you would return 0 when either word is not present, 0 would indicate that the words are neighbours. I would return -1 in that case.
• You seem to track too much state in acc, you can get away with just tracking the last matched word, the location of the last matched word and what the best distance has been thus far
• There are no comments whatsoever, I think your code could have used some

This is my functional approach:

const s = "dog cat hello cat dog dog hello cat dog world dog hello";
​
function smallestWordDistance(s, w1, w2) {
​
  function analyze(acc, word, index) {
​
    if (word == w1 || word == w2) {
​
      if (acc.word && acc.word != word) {
        const distance = index - acc.index - 1;
        acc.out = acc.out == -1 ? distance : Math.min(acc.out, distance);
      }
      acc.index = index;
      acc.word = word;
    }
    return acc;
  }
​
  return s.split(' ').reduce(analyze, { out: -1 }).out;
}
​
console.log(smallestWordDistance(s, "hello", "world"));

Answer 2

How about a single pass through the list of words. Have two variables to record the latest position you saw "hello" or "world", and when either occurs, compute the absolute difference between the positions, if it's a new record, update the record.