Categorías
Algorithms Interview

LeetCode – Word Ladder II (Java)

Dadas dos palabras (inicio y final) y un diccionario, busque todas las secuencias de transformación más cortas de principio a fin, de modo que: 1) Solo se puede cambiar una letra a la vez, 2) Cada palabra intermedia debe existir en el diccionario.

Por ejemplo, dado: start = «hit», end = «cog» y dict = [«hot»,»dot»,»dog»,»lot»,»log»], regreso:

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Solución Java

Esta es una extensión de Word Ladder. La idea es la misma. Para rastrear la escalera real, necesitamos agregar un puntero que apunte al nodo anterior en la clase WordNode. Además, la palabra utilizada no se puede eliminar directamente del diccionario. La palabra usada solo se elimina cuando cambian los pasos.

class Solution {
 
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new ArrayList<List<String>>();
 
        HashSet<String> unvisited = new HashSet<>();
        unvisited.addAll(wordList);
 
        LinkedList<Node> queue = new LinkedList<>();
        Node node = new Node(beginWord,0,null);
        queue.offer(node);
 
        int minLen = Integer.MAX_VALUE;
        while(!queue.isEmpty()){
            Node top = queue.poll();
 
            //top if have shorter result already
            if(result.size()>0 && top.depth>minLen){
                return result;
            }
 
            for(int i=0; i<top.word.length(); i++){
                char c = top.word.charAt(i);
                char[] arr = top.word.toCharArray();
                for(char j='z'; j>='a'; j--){
                    if(j==c){
                        continue;
                    }
                    arr[i]=j;
                    String t = new String(arr);
 
                    if(t.equals(endWord)){
                        //add to result
                        List<String> aResult = new ArrayList<>();
                        aResult.add(endWord);
                        Node p = top;
                        while(p!=null){
                            aResult.add(p.word);
                            p = p.prev;
                        }
 
                        Collections.reverse(aResult);
                        result.add(aResult);
 
                        //stop if get shorter result
                        if(top.depth<=minLen){
                            minLen=top.depth;
                        }else{
                            return result;
                        }
                    }
 
                    if(unvisited.contains(t)){
                        Node n=new Node(t,top.depth+1,top);
                        queue.offer(n);
                        unvisited.remove(t);
                    }
                }
            }
        }
 
        return result;
    }
}
 
class Node{
    public String word;
    public int depth;
    public Node prev;
 
    public Node(String word, int depth, Node prev){
        this.word=word;
        this.depth=depth;
        this.prev=prev;
    }
}

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 *