Este es un seguimiento de la Distancia entre palabras más corta. La única diferencia es que ahora se le proporciona la lista de palabras y su método será llamado repetidamente muchas veces con diferentes parámetros. ¿Cómo lo optimizarías?
Diseñe una clase que reciba una lista de palabras en el constructor e implemente un método que tome dos palabras palabra1 y palabra2 y devuelva la distancia más corta entre estas dos palabras en la lista.
Por ejemplo,
Suponga que palabras = [«practice», «makes», «perfect», «coding», «makes»].
Dado palabra1 = «codificación», palabra2 = «práctica», devuelve 3.
Dado palabra1 = «hace», palabra2 = «codificación», devuelve 1.
Solución Java
public class WordDistance { HashMap<String, ArrayList<Integer>> map; public WordDistance(String[] words) { map = new HashMap<String, ArrayList<Integer>>(); for(int i=0; i<words.length; i++){ if(map.containsKey(words[i])){ map.get(words[i]).add(i); }else{ ArrayList<Integer> list = new ArrayList<Integer>(); list.add(i); map.put(words[i], list); } } } public int shortest(String word1, String word2) { ArrayList<Integer> l1 = map.get(word1); ArrayList<Integer> l2 = map.get(word2); int result = Integer.MAX_VALUE; for(int i1: l1){ for(int i2: l2){ result = Math.min(result, Math.abs(i1-i2)); } } return result; } } |
La complejidad de tiempo para el método más corto es O (M * N), donde M es la frecuencia de la palabra1 y N es la frecuencia de la palabra2. Esto se puede mejorar de la siguiente manera:
public int shortest(String word1, String word2) { ArrayList<Integer> l1 = map.get(word1); ArrayList<Integer> l2 = map.get(word2); int result = Integer.MAX_VALUE; int i=0; int j=0; while(i<l1.size() && j<l2.size()){ result = Math.min(result, Math.abs(l1.get(i)-l2.get(j))); if(l1.get(i)<l2.get(j)){ i++; }else{ j++; } } return result; } |
La complejidad temporal del método más corto es ahora O (M + N). Dado que M + N
