更快地找到数组中单词之间的最小距离

Consider I have this array:

$array = array(

'word1',
'abc',
'abc',
'word2',
 [other words]
'word1',
'dfg'
'word2',
 [other words]
);

I need to find the minimum distance between 2 given words. (let 'word1' and 'word2' be these 2 words)

In this case the minium distance between word1 and word2 is 1 because in the second group of words they are separated by only 'dfg'.

I wrote a simple code but it's too expsensive and I am looking for a faster version.

//> PSEUDO CODE
function minDistance( $words, $word1, $word2 ) {
    foreach( $words as $k=>$v) 
      if ( $v == $words1 )
         $positionsOfFirstWord[] = $k;

      if ( $v == $words2 )
         $positionsOfSecondWord[] = $k;


     //> If word1 or word2 was not found in the array then
     //> return max distance possibile (count($words))

     //> Now we have 2 array containg the position of both word we need.

     foreach( $positionsOfFirstWord as $v )
        foreach( $positionsOfSecondWord as $vv )
          $distance = abs($vv-$v);

}

Note the order of words in $array isn't important (that's why there is abs())

Do you think there could be a better version?

Please note the function must return 1 in this case too:

array(
 [other words]
'word2',
'dfg',
'word1'
 [other words]
);

I think a simple loop is enough. Keep track over the current minimum and of the last word1 and update current minimum if a word2 is found. Basically you are utilizing the fact that a word2 will always be closest to the last word1 found

 let minimum = INFINITY
 let lastword1 = -1
 let lastword2 =  -1
 foreach word w in words
 {

      if ( w is word1 )
      {
           lastword1 = current position;

           find distance between lastword2 and w update minimum if needed
      }

      if ( w is word2 )
      {
          lastword2 = current position;

          find distance between lastword1 and w update minimum if needed
      }

 }

You can do this in O(n) but there might faster ways if pre processing can be done and you need to answer multiple queries

why set up an array for the positions? Why not just save them as values and then do absolute value of the difference?

function distance($words, $first, $second) {

  $result = new Array();

  for(i=0; i<words.length; i++) {
    if($words[i] == $first) {
      $firstPos = i;
    } elseif($words[i] == $second) {
      $secondPos = i;
      $result[] = (abs($firstPos - $secondPos));
    }
  }

  // Find the smallest number in the result array
  $min = $result[0];
  for(i=0; i<result.length; i++) {
    if(result[i] < $min) {
      $min = result[i];
    }
  }

  return $min;

}

Based on parapura I wrote this, Dunno why but it seems it's working SLOWER

function minDistance2($words,$key1,$key2) {

    if ($key1 == $key2)
        return 0;

    $min = false;
    $p1 = false;
    $p2 = false;

    foreach($words as $k=>$v) {
        $calc = false;

        if ($v == $key1) {
            $p1 = $k;       
            $calc = true;
        } else if ($v == $key2) {
            $p2 = $k;
            $calc = true;
        }

        if ($calc) {
            if ($p1===false || $p2===false)
                continue;

            $d = abs($p1-$p2) - 1;

            if ($min === false || $d<$min )
                $min = $d;
        }

        if ($min!==false && $min<=0)
            return 0;
    }

    return ($min===false ? 0 : $min);
}

construct an array of ints as follows

1. iterate over array of words from top to bottom
2. if you encounter 'word1' and the last word encountered was not 'word1' then append the position to the array being constructed
3. if you encounter 'word2' and the last word encountered was not 'word2' then append the position to the array being constructed
4. if you encounter 'word2' and the last word encountered was 'word2' then update the last element of the array to the current position

now scan the array to find the minimum difference between any two pairs

repeat this process one more time except do step 4. with 'word1' instead of 'word2'

your answer is the smaller of the two minimums