Thursday, May 28, 2015

L Question: find Minimum distance in a dictonary

public class WordFinder {
 private Map<String, ArrayList<Integer>> dictionary = new HashMap<String, ArrayList<Integer>>();

 public WordFinder(String[] list) {
  for (int i = 0; i < list.length; i++) {
   addToDictionary(list[i], i);
  }
 }

 private void addToDictionary(String word, int position) {
  ArrayList<Integer> positions = dictionary.get(word);
  if (positions == null) {
   positions = new ArrayList<Integer>();
  }

  positions.add(position);
  dictionary.put(word, positions);
 }

 public int findDistance(String a, String b) {
  if (a == null || b == null) {
   return -1;
  }

  if (a.equals(b)) {
   return 0;
  }
  ArrayList<Integer> posA = dictionary.get(a);
  ArrayList<Integer> posB = dictionary.get(b);
  if (posA == null || posB == null) {
   return -1;
  }

  int min = 0;
  for (int x : posA) {
   for (int y : posB) {
    int distance = Math.abs(x - y);
    if (min > distance || min == 0) {
     min = distance;
    }
   }
  }

  return min;
 }

 public static int findDistanceBetweenWords(String inputBody, String pair1, String pair2) {
        if (inputBody.isEmpty() || pair1.isEmpty() || pair2.isEmpty()) {
            return -1;
        }
        if (pair1.equals(pair2)) {
            return 0;
        }
        StringTokenizer stringTokenizer = new StringTokenizer(inputBody, " ");
        int distance = 0, globalDistance = Integer.MAX_VALUE;
        String token;
        while (stringTokenizer.hasMoreTokens()) {
            token = stringTokenizer.nextToken();
            if (token.equals(pair1)) {
                distance = 0;
            } else if (token.equals(pair2)) {
                globalDistance = Math.min(distance, globalDistance);
            }
            distance++;
        }
        if (globalDistance == Integer.MAX_VALUE || globalDistance == 0) {
            return -1;
        } else {
            return globalDistance;
        }
    }

No comments:

Post a Comment