CODEWITHSUNDEEP
javaalgorithm
John Roberts
John Roberts

Reputation: 5966

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 the following solution, which appears to be O(n), but I'm not sure if there is a better solution out there. Does anyone have any 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;
        }
    }
}

Upvotes: 8

Views: 12240

Answers (8)

Vishwajeet Singh
Vishwajeet Singh

Reputation: 1

With only one while loop without any DS and internal method like Math class etc. Time complexity: O(n) PFB the code:

public class MinimumDistanceBetweenTheGivenTwoWords {
private void minimumDistanceBetweenTwoWords(String[] statement, String word1, String word2) {

 int firstCounter=0; int secondCounter=0;
 int i=0;
 while (i<statement.length-1){
     if(statement[i].equalsIgnoreCase(word1)){
         firstCounter = i;
     }
     if(statement[i+1].equalsIgnoreCase(word2)){
         secondCounter = i+1;
     }
     i++;
 }
    int shortestDistance = secondCounter-firstCounter;
    System.out.println("Shortest distance: "+shortestDistance);
}

public static void main(String[] args) {
    MinimumDistanceBetweenTheGivenTwoWords obj = new MinimumDistanceBetweenTheGivenTwoWords();
    String[] statement = {"the", "quick", "brown", "fox", "quick"};
    obj.minimumDistanceBetweenTwoWords(statement1, "the", "fox");
}
}

Upvotes: 0

greybeard
greybeard

Reputation: 2467

any ideas?

You "duplicated" code: Keep DRY: Don't Repeat Yourself

double
    distance,
    minDistance = Double.POSITIVE_INFINITY;
for (int x = 0 ; x < strings.length ; x++)
    if (strings[x].equals(targetString))
        for (int y = 0 ; y < strings.length ; y++)
            if (x != y && strings[y].equals(targetString2)) {
                if (minDistance > (distance = Math.abs(y - x)))
                    minDistance = distance;
                if (x < y)
                    break;
            }

You missed opportunities to stop iterating early:

minDistance = strings.length;
if (java.util.Arrays.asList(strings).contains(targetString2))
    for (int x = 0 ; x < strings.length ; x++) {
        if (!strings[x].equals(targetString))
            continue;
        for (int y = x, limit = Math.min(strings.length, x + minDistance) ; ++y < limit ; )
            if (strings[y].equals(targetString2)) {
                minDistance = y - x;
                break;  // higher values of y won't decrease y - x
            }
        for (int y = x, limit = Math.max(-1, x - minDistance) ; limit < --y ; )
            if (strings[y].equals(targetString2)) {
                minDistance = x - y;
                break;  // lower values of y won't decrease x - y
            }
        if (minDistance < 2)
            break;
    }

Upvotes: 0

Rohit Ranjan
Rohit Ranjan

Reputation: 1

  private static Integer getDistance(String first, String second, String given) {
    String[] splitGiven = given.split(" ");
    int firstWord;
    int secondWord;
    int result;
    List<Integer> suspectedDistances = new ArrayList<>();
    for (int i = 0; i < splitGiven.length; i++) {
      if (Objects.equals(splitGiven[i], first)) {
        firstWord = i;
       
        for (int j = 0; j < splitGiven.length; j++) {
          if (Objects.equals(splitGiven[j], second)) {
            secondWord = j;
            
            suspectedDistances.add(secondWord - firstWord);
          }
        }
      }
    }
  
    Collections.sort(suspectedDistances);
    result = suspectedDistances.get(0);
    if ((splitGiven[0].equals(first) || splitGiven[0].equals(second)) &&
        (splitGiven[splitGiven.length - 1].equals(first) || splitGiven[splitGiven.length - 1].equals(second))) {
      result = 1;
    }
    return result;
  }

Upvotes: 0

Popeye
Popeye

Reputation: 263

Just 1 iteration. Very Simple Solution Assumptions : str1 and str2 are not null. str1 not equal to str2. strs does not contains null;

    private static int findShortestDistance(String str1, String str2, String[] strs) {
        int distance = Integer.MAX_VALUE;
        String temp = null;
        int index = 0;
        for(int i=0; i<strs.length; ++i) {
          if(str1.equals(strs[i]) || str2.equals(strs[i])) {
             if(temp != null && !strs[i].equals(temp)) {
                distance = Math.min(distance, i - index);
             }
             temp = strs[i];
             index = i;
           }
        }
     return distance;
    }

Upvotes: 0

sarjit07
sarjit07

Reputation: 10569

Better and simple solution for finding minimum distance between two words in a given paragraph.

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

Time Complexity: O(n)
Space COmplexity: O(1)

Upvotes: 0

alejandro
alejandro

Reputation: 2847

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

Upvotes: 3

nem035
nem035

Reputation: 35481

You solution is O(N^2) because you traverse the whole list when finding each word. First you find the first word and then again traverse the whole list to find the second word.

What you can do is use two variables to keep track of the position of each word and calculate the distance with a single pass through the list => 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);

Upvotes: 16

Keshav
Keshav

Reputation: 1

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**

Upvotes: 0

Related Questions