Finding distanza minima tra le parole in un array

Question

Esempio:

WordDistanceFinder finder = new WordDistanceFinder (Arrays.asList ("il", "veloce", "marrone", "volpe", "rapida"));

assert (finder.distance ("fox", "the") == 3);

assert (finder.distance ("quick", "fox") == 1);

Ho la seguente soluzione, che sembra essere O (n), ma non sono sicuro che esista una soluzione migliore. Qualcuno ha qualche idea?

String targetString = "fox"; 
String targetString2 = "the"; 
double minDistance = Double.POSITIVE_INFINITY; 
for(int x = 0; x < strings.length; x++){ 
    if(strings[x].equals(targetString)){ 
     for(int y = x; y < strings.length; y++){ 
      if(strings[y].equals(targetString2)) 
       if(minDistance > (y - x)) 
        minDistance = y - x; 
     } 
     for(int y = x; y >=0; y--){ 
      if(strings[y].equals(targetString2)) 
       if(minDistance > (x - y)) 
        minDistance = x - y; 
     } 
    } 
} 

Answer 1

soluzione Si è O(N^2) perché si attraversano l'intera lista quando trovare ogni parola. Prima trovi la prima parola e poi attraversa di nuovo l'intera lista per trovare la seconda parola.

Che cosa si può fare è usare due variabili per tenere traccia della posizione di ogni parola e calcolare la distanza con un unico passaggio l'elenco =>O(N).

int index1 = -1; 
int index2 = -1; 
int minDistance = Integer.MAX_VALUE; 
int tempDistance = 0; 

for (int x = 0; x < strings.length; x++) { 
    if (strings[x].equals(targetString)) { 
     index1 = x; 
    } 
    if (strings[x].equals(targetString2)) { 
     index2 = x; 
    } 
    if (index1 != -1 && index2 != -1) { // both words have to be found 
     tempDistance = (int) Math.abs(index2 - index1); 
     if (tempDistance < minDistance) { 
      minDistance = tempDistance; 
     } 
    } 
} 

System.out.println("Distance:\t" + minDistance); 

Answer 2

import java.util.*; 
public class WordDistance { 

    public static void main(String[] args) { 
     Scanner in=new Scanner(System.in); 
     String s=in.nextLine(); 
     String s1=in.nextLine(); 
     String s2=in.nextLine(); 
     int index1=-1; 
     int index2=-1; 
     boolean flag1=false; 
     boolean flag2=false; 
     int distance=Integer.MAX_VALUE; 
     int answer=Integer.MAX_VALUE; 
     String[] sarray=s.split(" "); 
     for(int i=0;i<sarray.length;i++) 
     { 
      if(!s1.equals(s2)) 
      { 
       flag1=false; flag2=false; 
      } 
      if(s1.equals(sarray[i]) && flag1==false) 
      { 
       index1=i; 
       flag1=true; 
      } 
      else 
      if(s2.equals(sarray[i]) && flag2==false) 
      { 
        index2=i; 
        flag2=true; 
      } 
      if(index1!=-1 && index2!=-1) 
      { 
       distance=Math.abs(index1-index2); 
       flag1=false; flag2=false; 
      } 
      if(distance<answer) 
      { 
       answer=distance; 
      } 
     } 
     if(answer==Integer.MAX_VALUE) 
     { 
      System.out.print("Words not found"); 
     } 
     else 
     { 
      System.out.print(answer); 
     } 
    } 
} 

//**Test Case 1**: the quick the brown quick brown the frog (frog brown) **O/P 2** 
//**Test Case 2**: the quick the brown quick brown the frog (brown brown) **O/P 2** 
//**Test Case 3**: the brown qucik frog quick the (the quick) **O/P 1** 

Answer 3

migliore e soluzione semplice per la ricerca di distanza minima tra due parole in un determinato punto.

String[] strArray = {"the","quick","brown","fox","quick"}; 
    String str1 = "quick"; 
    String str2 = "fox"; 
    int i,startIndex=0,minDistnace=100; 
    for(i=0;i<strArray.length;i++){ 
     if(strArray[i].equals(str1)||strArray[i].equals(str2)){ 
      startIndex = i;   //get the first occurence of either word 
      break; 
     } 
    } 
    for(;i<strArray.length;i++){ 
     if(strArray[i].equals(str1)||strArray[i].equals(str2)){ 
      //compare every word from that first occurence 
      // if words not same and distance less than minimun distance then update 
      if(!strArray[i].equals(strArray[startIndex]) && (i-startIndex)<minDistance){ 
       minDistance = i-startIndex; 
       startIndex =i; 
      } 
      else{ 
       startIndex =i; 
      } 
     } 
    } 
    System.out.println(minDistance); 

complessità temporale: O (n)
complessità spaziale: O (1)

Answer 4

function findMinimumWordDistance(words, wordA, wordB) { 
    var wordAIndex = null; 
    var wordBIndex = null; 
    var minDinstance = null; 

    for (var i = 0, length = words.length; i < length; i++) { 
    if (words[i] === wordA) { 
     wordAIndex = i; 
    } 

    if (words[i] === wordB) { 
     wordBIndex = i; 
    } 

    if (wordAIndex !== null && wordBIndex !== null) { 
     var distance = Math.abs(wordAIndex - wordBIndex); 
     if(minDinstance === null || minDinstance > distance) { 
     minDinstance = distance; 
     } 
    } 
    } 
    return minDinstance; 
}