Categorías
Algorithms

LeetCode – Distancia de palabra más corta II (Java)

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;
    }
}
  LeetCode - Prefijo común más largo (Java)

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

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *