java - Finding Minimum Distance Between Words in An Array -

java - Finding Minimum Distance Between Words in An Array -

example:

worddistancefinder finder = new worddistancefinder(arrays.aslist("the", "quick", "brown", "fox", "quick"));

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

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

i have next solution, appears o(n), i'm not sure if there improve solution out there. have ideas?

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; } } }

you solution o(n^2) because traverse whole list when finding each word. first find first word , 1 time again traverse whole list find sec word.

what can utilize 2 variables maintain track of position of each word , calculate distance single pass through list => o(n).

int index1 = -1, index2 = -1; int mindistance = integer.max_value, tempdistance = 0; (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 found tempdistance = (int) math.abs(index2 - index1); if (tempdistance < mindistance) { mindistance = tempdistance; } } } system.out.println("distance:\t" + mindistance);

java algorithm