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; } } |