Dado un diccionario, y dos palabras start y target (ambas de la misma longitud). Encuentre la longitud de la string más pequeña desde el principio hasta el destino , si existe, de modo que las palabras adyacentes en la string solo difieran en un carácter y cada palabra en la string sea una palabra válida, es decir, existe en el diccionario. Se puede suponer que la palabra objetivo existe en el diccionario y que las longitudes de todas las palabras del diccionario son iguales.
Ejemplos:
Entrada: Diccionario = {POON, PLEE, SAME, POIE, PLEA, PLIE, POIN}
start = “TOON”
target = “PLEA”
Salida: 7
TOON -> POON –> POIN –> POIE –> PLIE –> PLEE –> PETICIÓN
Enfoque: este problema se puede resolver utilizando el enfoque BFS estándar como se describe aquí, pero su rendimiento se puede mejorar mediante el uso de BFS bidireccional.
BFS bidireccional no reduce la complejidad del tiempo de la solución, pero definitivamente optimiza el rendimiento en muchos casos. Este enfoque también se puede usar en muchos otros problemas de búsqueda de ruta más cortos donde tenemos suficiente información sobre el origen y el Node de destino. La idea básica involucrada en BFS bidireccional es comenzar la búsqueda desde ambos extremos de la ruta.
Por lo tanto, se necesitan mantener dos colas y dos arrays visitadas para rastrear ambas rutas. Entonces, cada vez que un Node (digamos A) está presente en la cola de origen, encuentra un Node (digamos B) que está presente en la cola de destino, entonces podemos calcular la respuesta sumando la distancia de A desde la fuente y la distancia de B desde el objetivo menos 1 (un Node es común). De esta manera podemos calcular la respuesta en la mitad del tiempo en comparación con el enfoque BFS estándar. Este método también se conoce como el enfoque BFS de encuentro en el medio.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Structure for queue
struct node {
string word;
int len;
};
// Function that returns true if a and b
// differ in only a single character
bool isAdj(string a, string b)
{
int count = 0;
for (int i = 0; i < a.length(); i++) {
if (a[i] != b[i])
count++;
}
if (count == 1)
return true;
return false;
}
// Function to return the length of the shortest
// chain from ‘beginWord’ to ‘endWord’
int ladderLength(string beginWord, string endWord,
vector<string>& wordList)
{
/* q1 is used to traverse the graph from beginWord
and q2 is used to traverse the graph from endWord.
vis1 and vis2 are used to keep track of the
visited states from respective directions */
queue<node> q1;
queue<node> q2;
unordered_map<string, int> vis1;
unordered_map<string, int> vis2;
node start = { beginWord, 1 };
node end = { endWord, 1 };
vis1[beginWord] = 1;
q1.push(start);
vis2[endWord] = 1;
q2.push(end);
while (!q1.empty() && !q2.empty()) {
// Fetch the current node
// from the source queue
node curr1 = q1.front();
q1.pop();
// Fetch the current node from
// the destination queue
node curr2 = q2.front();
q2.pop();
// Check all the neighbors of curr1
for (auto it = wordList.begin(); it != wordList.end(); it++) {
// If any one of them is adjacent to curr1
// and is not present in vis1
// then push it in the queue
if (isAdj(curr1.word, *it) && vis1.count(*it) == false) {
node temp = { *it, curr1.len + 1 };
q1.push(temp);
vis1[*it] = curr1.len + 1;
// If temp is the destination node
// then return the answer
if (temp.word == endWord) {
return temp.len;
}
// If temp is present in vis2 i.e. distance from
// temp and the destination is already calculated
if (vis2.count(temp.word)) {
return temp.len + vis2[temp.word] - 1;
}
}
}
// Check all the neighbors of curr2
for (auto it = wordList.begin(); it != wordList.end(); it++) {
// If any one of them is adjacent to curr2
// and is not present in vis1 then push it in the queue.
if (isAdj(curr2.word, *it) && vis2.count(*it) == false) {
node temp = { *it, curr2.len + 1 };
q2.push(temp);
vis2[*it] = curr2.len + 1;
// If temp is the destination node
// then return the answer
if (temp.word == beginWord) {
return temp.len;
}
// If temp is present in vis1 i.e. distance from
// temp and the source is already calculated
if (vis1.count(temp.word)) {
return temp.len + vis1[temp.word] - 1;
}
}
}
}
return 0;
}
// Driver code
int main()
{
vector<string> wordList;
wordList.push_back("poon");
wordList.push_back("plee");
wordList.push_back("same");
wordList.push_back("poie");
wordList.push_back("plie");
wordList.push_back("poin");
wordList.push_back("plea");
string start = "toon";
string target = "plea";
cout << ladderLength(start, target, wordList);
return 0;
}
Java
import java.util.*;
public class GFG
{
public static class node
{
String word;
int len;
public node(String word, int len)
{
this.word = word;
this.len = len;
}
}
public static boolean isAdj(String a, String b)
{
int count = 0;
for (int i = 0; i < a.length(); i++)
{
if (a.charAt(i) != b.charAt(i))
count++;
}
if (count == 1)
return true;
return false;
}
// Function to return the length of the shortest
// chain from 'beginWord' to 'endWord'
public static int ladderLength(String beginWord, String endWord,
ArrayList<String> wordList)
{
/* q1 is used to traverse the graph from beginWord
and q2 is used to traverse the graph from endWord.
vis1 and vis2 are used to keep track of the
visited states from respective directions */
Queue<node> q1 = new LinkedList<>();
Queue<node> q2 = new LinkedList<>();
HashMap<String, Integer> vis1 = new HashMap<>();
HashMap<String, Integer> vis2 = new HashMap<>();
node start = new node(beginWord, 1);
node end = new node(endWord, 1);
vis1.put(beginWord, 1);
q1.add(start);
vis2.put(endWord, 1);
q2.add(end);
while (q1.size() > 0 && q2.size() > 0)
{
// Fetch the current node
// from the source queue
node curr1 = q1.remove();
// Fetch the current node from
// the destination queue
node curr2 = q2.remove();
// Check all the neighbors of curr1
for (int i = 0; i < wordList.size(); i++)
{
// If any one of them is adjacent to curr1
// and is not present in vis1
// then push it in the queue
if (isAdj(curr1.word,wordList.get(i)) &&
vis1.containsKey(wordList.get(i)) == false)
{
node temp = new node(wordList.get(i),
curr1.len + 1);
q1.add(temp);
vis1.put(wordList.get(i), curr1.len + 1);
// If temp is the destination node
// then return the answer
if (temp.word.equals(endWord))
{
return temp.len;
}
// If temp is present in vis2 i.e. distance from
// temp and the destination is already calculated
if (vis2.containsKey(temp.word))
{
return temp.len + vis2.get(temp.word) - 1;
}
}
}
// Check all the neighbors of curr2
for (int i = 0; i < wordList.size(); i++)
{
// If any one of them is adjacent to curr2
// and is not present in vis1 then push it in the queue.
if (isAdj(curr2.word,wordList.get(i)) &&
vis2.containsKey(wordList.get(i)) == false)
{
node temp = new node(wordList.get(i),
curr2.len + 1 );
q2.add(temp);
vis2.put(wordList.get(i), curr2.len + 1);
// If temp is the destination node
// then return the answer
if (temp.word.equals(beginWord))
{
return temp.len;
}
// If temp is present in vis1 i.e. distance from
// temp and the source is already calculated
if (vis1.containsKey(temp.word))
{
return temp.len + vis1.get(temp.word) - 1;
}
}
}
}
return 0;
}
// Driver code
public static void main(String args[])
{
ArrayList<String> wordList = new ArrayList<>();
wordList.add("poon");
wordList.add("plee");
wordList.add("same");
wordList.add("poie");
wordList.add("plie");
wordList.add("poin");
wordList.add("plea");
String start = "toon";
String target = "plea";
System.out.println(ladderLength(start, target, wordList));
}
}
// This code is contributed by Sambhav Jain
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
class node
{
public String word;
public int len;
public node(String word, int len)
{
this.word = word;
this.len = len;
}
}
public static bool isAdj(String a, String b)
{
int count = 0;
for (int i = 0; i < a.Length; i++)
{
if (a[i] != b[i])
count++;
}
if (count == 1)
return true;
return false;
}
// Function to return the length of the shortest
// chain from 'beginWord' to 'endWord'
public static int ladderLength(String beginWord, String endWord,
List<String> wordList)
{
/* q1 is used to traverse the graph from beginWord
and q2 is used to traverse the graph from endWord.
vis1 and vis2 are used to keep track of the
visited states from respective directions */
Queue<node> q1 = new Queue<node>();
Queue<node> q2 = new Queue<node>();
Dictionary<String, int> vis1 = new Dictionary<String, int>();
Dictionary<String, int> vis2 = new Dictionary<String, int>();
node start = new node(beginWord, 1);
node end = new node(endWord, 1);
vis1.Add(beginWord, 1);
q1.Enqueue(start);
vis2.Add(endWord, 1);
q2.Enqueue(end);
while (q1.Count > 0 && q2.Count > 0)
{
// Fetch the current node
// from the source queue
node curr1 = q1.Dequeue();
// Fetch the current node from
// the destination queue
node curr2 = q2.Dequeue();
// Check all the neighbors of curr1
for (int i = 0; i < wordList.Count; i++)
{
// If any one of them is adjacent to curr1
// and is not present in vis1
// then push it in the queue
if (isAdj(curr1.word,wordList[i]) &&
vis1.ContainsKey(wordList[i]) == false)
{
node temp = new node(wordList[i],
curr1.len + 1);
q1.Enqueue(temp);
vis1.Add(wordList[i], curr1.len + 1);
// If temp is the destination node
// then return the answer
if (temp.word.Equals(endWord))
{
return temp.len;
}
// If temp is present in vis2 i.e. distance from
// temp and the destination is already calculated
if (vis2.ContainsKey(temp.word))
{
return temp.len + vis2[temp.word] - 1;
}
}
}
// Check all the neighbors of curr2
for (int i = 0; i < wordList.Count; i++)
{
// If any one of them is adjacent to curr2
// and is not present in vis1 then push it in the queue.
if (isAdj(curr2.word,wordList[i]) &&
vis2.ContainsKey(wordList[i]) == false)
{
node temp = new node(wordList[i],
curr2.len + 1 );
q2.Enqueue(temp);
vis2.Add(wordList[i], curr2.len + 1);
// If temp is the destination node
// then return the answer
if (temp.word.Equals(beginWord))
{
return temp.len;
}
// If temp is present in vis1 i.e. distance from
// temp and the source is already calculated
if (vis1.ContainsKey(temp.word))
{
return temp.len + vis1[temp.word] - 1;
}
}
}
}
return 0;
}
// Driver code
public static void Main(String []args)
{
List<String> wordList = new List<String>();
wordList.Add("poon");
wordList.Add("plee");
wordList.Add("same");
wordList.Add("poie");
wordList.Add("plie");
wordList.Add("poin");
wordList.Add("plea");
String start = "toon";
String target = "plea";
Console.WriteLine(ladderLength(start, target, wordList));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python 3 implementation of the approach
from collections import deque as dq
# class for queue
class node :
def __init__(self, w, l):
self.word=w
self.len=l
# Function that returns true if a and b
# differ in only a single character
def isAdj(a, b):
count = 0
for i in range(len(a)):
if (a[i] != b[i]):
count+=1
if (count == 1):
return True
return False
# Function to return the length of the shortest
# chain from ‘beginWord’ to ‘endWord’
def ladderLength(beginWord, endWord, wordList):
# q1 is used to traverse the graph from beginWord
# and q2 is used to traverse the graph from endWord.
# vis1 and vis2 are used to keep track of the
# visited states from respective directions
q1=dq([])
q2=dq([])
vis1=dict()
vis2=dict()
start = node(beginWord, 1)
end = node(endWord, 1)
vis1[beginWord] = 1
q1.append(start)
vis2[endWord] = 1
q2.append(end)
while (q1 and q2):
# Fetch the current node
# from the source queue
curr1 = q1.popleft()
# Fetch the current node from
# the destination queue
curr2 = q2.popleft()
# Check all the neighbors of curr1
for it in wordList:
# If any one of them is adjacent to curr1
# and is not present in vis1
# then push it in the queue
if (isAdj(curr1.word, it) and it not in vis1) :
temp = node(it, curr1.len + 1)
q1.append(temp)
vis1[it] = curr1.len + 1
# If temp is the destination node
# then return the answer
if (temp.word == endWord) :
return temp.len
# If temp is present in vis2 i.e. distance from
# temp and the destination is already calculated
if temp.word in vis2 :
return temp.len + vis2[temp.word] - 1
# Check all the neighbors of curr2
for it in wordList:
# If any one of them is adjacent to curr2
# and is not present in vis1 then push it in the queue.
if (isAdj(curr2.word, it) and it not in vis2) :
temp = node(it, curr2.len + 1)
q2.append(temp)
vis2[it] = curr2.len + 1
# If temp is the destination node
# then return the answer
if (temp.word == beginWord) :
return temp.len
# If temp is present in vis1 i.e. distance from
# temp and the source is already calculated
if temp.word in vis1:
return temp.len + vis1[temp.word] - 1
return 0
# Driver code
if __name__=='__main__':
wordList=[]
wordList.append("poon")
wordList.append("plee")
wordList.append("same")
wordList.append("poie")
wordList.append("plie")
wordList.append("poin")
wordList.append("plea")
start = "toon"
target = "plea"
print(ladderLength(start, target, wordList))
Producción:
7
Complejidad de tiempo : O(N^2), donde N es la longitud de la string.
Espacio Auxiliar : O(N).
Publicación traducida automáticamente
Artículo escrito por TarunDhankhar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA