Categorías
Algorithms Interview

LeetCode – Subcadena con concatenación de todas las palabras (Java)

Se le da una cadena, s, y una lista de palabras, palabras, que tienen la misma longitud. Encuentre todos los índices iniciales de subcadena (s) en s que sea una concatenación de cada palabra en palabras exactamente una vez y sin ningún carácter intermedio.

Por ejemplo, dado: s = «barfoothefoobarman» & words =[«foo», «bar»], regreso [0,9].

Análisis

Este problema es similar (casi el mismo) a la subcadena más larga que contiene 2 caracteres únicos.

Dado que cada palabra del diccionario tiene la misma longitud, cada una de ellas puede tratarse como un solo carácter.

Solución Java

public List<Integer> findSubstring(String s, String[] words) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    if(s==null||s.length()==0||words==null||words.length==0){
        return result;
    } 
 
    //frequency of words
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    for(String w: words){
        if(map.containsKey(w)){
            map.put(w, map.get(w)+1);
        }else{
            map.put(w, 1);
        }
    }
 
    int len = words[0].length();
 
    for(int j=0; j<len; j++){
        HashMap<String, Integer> currentMap = new HashMap<String, Integer>();
        int start = j;//start index of start
        int count = 0;//count totoal qualified words so far
 
        for(int i=j; i<=s.length()-len; i=i+len){
            String sub = s.substring(i, i+len);
            if(map.containsKey(sub)){
                //set frequency in current map
                if(currentMap.containsKey(sub)){
                    currentMap.put(sub, currentMap.get(sub)+1);
                }else{
                    currentMap.put(sub, 1);
                }
 
                count++;
 
                while(currentMap.get(sub)>map.get(sub)){
                    String left = s.substring(start, start+len);
                    currentMap.put(left, currentMap.get(left)-1);
 
                    count--;
                    start = start + len;
                }
 
 
                if(count==words.length){
                    result.add(start); //add to result
 
                    //shift right and reset currentMap, count & start point         
                    String left = s.substring(start, start+len);
                    currentMap.put(left, currentMap.get(left)-1);
                    count--;
                    start = start + len;
                }
            }else{
                currentMap.clear();
                start = i+len;
                count = 0;
            }
        }
    }
 
    return result;
}

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 *