Dadas dos strings inicio y destino (ambas de la misma longitud) y una lista de strings str[] , la tarea es imprimir todas las secuencias más pequeñas posibles comenzando desde el inicio hasta el destino si existe, de modo que las palabras adyacentes en la secuencia solo se diferencien por un solo carácter y cada palabra en la secuencia está presente en la lista dada.
Nota: se puede suponer que la palabra objetivo está presente en la lista y que la longitud de todas las palabras es la misma. Si ocurren varias secuencias, imprímalas todas.
Ejemplo:
Entrada: str[] = {poon, plee, mismo, poie, plea, plie, point}, start = «toon», target = «plea»
Salida: [[toon, poon, poin, poie, plee, plea]]
Explicación: toon → poon → punto → poie → plee → súplicaEntrada: str[] = { ted, tex, red, tax, tad, den, rex, pee}, start = “red”, target = “tax”
Salida [[“red”, “ted”, “tad”, “impuesto”], [“rojo”, “ted”, “tex”, “impuesto”], [“rojo”, “rex”, “tex”, “impuesto”]]
Enfoque: el problema se puede resolver usando BFS . La parte difícil aquí es hacer el BFS de la ruta en lugar de las palabras. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos res , para almacenar todas las rutas más cortas posibles.
- Cree un Conjunto para almacenar todas las palabras visitadas en la ruta actual y una vez que se complete la ruta actual, borre todas las palabras visitadas.
- Para cada palabra actual, encuentre las siguientes palabras posibles presentes en str[] cambiando cada carácter de ‘a’ a ‘z’ y encuentre todas las rutas posibles.
- Finalmente, imprime todas las rutas posibles.
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print all possible shortest
// sequences starting from start to target.
void displaypath(vector<vector<string> >& res)
{
for (int i = 0; i < res.size(); i++) {
cout << "[ ";
for (int j = 0; j < res[0].size(); j++) {
cout << res[i][j] << ", ";
}
cout << " ]\n";
}
}
// Find words differing by a single
// character with word
vector<string> addWord(
string word,
unordered_set<string>& dict)
{
vector<string> res;
// Find next word in dict by changing
// each element from 'a' to 'z'
for (int i = 0; i < word.size(); i++) {
char s = word[i];
for (char c = 'a'; c <= 'z'; c++) {
word[i] = c;
if (dict.count(word))
res.push_back(word);
}
word[i] = s;
}
return res;
}
// Function to get all the shortest possible
// sequences starting from 'start' to 'target'
vector<vector<string> > findLadders(
vector<string>& Dict,
string beginWord,
string endWord)
{
// Store all the shortest path.
vector<vector<string> > res;
// Store visited words in list
unordered_set<string> visit;
// Queue used to find the shortest path
queue<vector<string> > q;
// Stores the distinct words from given list
unordered_set<string> dict(Dict.begin(),
Dict.end());
q.push({ beginWord });
// Stores whether the shortest
// path is found or not
bool flag = false;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
// Explore the next level
vector<string> cur = q.front();
q.pop();
vector<string> newadd;
// Find words differing by a
// single character
newadd = addWord(cur.back(), dict);
// Add words to the path.
for (int j = 0; j < newadd.size(); j++) {
vector<string> newline(cur.begin(),
cur.end());
newline.push_back(newadd[j]);
// Found the target
if (newadd[j] == endWord) {
flag = true;
res.push_back(newline);
}
visit.insert(newadd[j]);
q.push(newline);
}
}
// If already reached target
if (flag) {
break;
}
// Erase all visited words.
for (auto it : visit) {
dict.erase(it);
}
visit.clear();
}
return res;
}
// Driver Code
int main()
{
vector<string> str{ "ted", "tex", "red",
"tax", "tad", "den",
"rex", "pee" };
string beginWord = "red";
string endWord = "tax";
vector<vector<string> > res
= findLadders(str, beginWord, endWord);
displaypath(res);
}
Python3
# Python Program to implement
# the above approach
from collections import deque
from typing import Deque, List, Set
# Function to print all possible shortest
# sequences starting from start to target.
def displaypath(res: List[List[str]]):
for i in res:
print("[ ", end="")
for j in i:
print(j, end=", ")
print("]")
# Find words differing by a single
# character with word
def addWord(word: str, Dict: Set):
res: List[str] = []
wrd = list(word)
# Find next word in dict by changing
# each element from 'a' to 'z'
for i in range(len(wrd)):
s = wrd[i]
c = 'a'
while c <= 'z':
wrd[i] = c
if ''.join(wrd) in Dict:
res.append(''.join(wrd))
c = chr(ord(c) + 1)
wrd[i] = s
return res
# Function to get all the shortest possible
# sequences starting from 'start' to 'target'
def findLadders(Dictt: List[str], beginWord: str, endWord: str):
# Store all the shortest path.
res: List[List[str]] = []
# Store visited words in list
visit = set()
# Queue used to find the shortest path
q: Deque[List[str]] = deque()
# Stores the distinct words from given list
Dict = set()
for i in Dictt:
Dict.add(i)
q.append([beginWord])
# Stores whether the shortest
# path is found or not
flag = False
while q:
size = len(q)
for i in range(size):
# Explore the next level
cur = q[0]
q.popleft()
newadd = []
# Find words differing by a
# single character
newadd = addWord(cur[-1], Dict)
# Add words to the path.
for j in range(len(newadd)):
newline = cur.copy()
newline.append(newadd[j])
# Found the target
if (newadd[j] == endWord):
flag = True
res.append(newline)
visit.add(newadd[j])
q.append(newline)
# If already reached target
if (flag):
break
# Erase all visited words.
for it in visit:
Dict.remove(it)
visit.clear()
return res
# Driver Code
if __name__ == "__main__":
string = ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"]
beginWord = "red"
endWord = "tax"
res = findLadders(string, beginWord, endWord)
displaypath(res)
# This code is contributed by sanjeev2552
[ red, ted, tad, tax, ] [ red, ted, tex, tax, ] [ red, rex, tex, tax, ]
Complejidad temporal: O(N²*M), donde M es el número de strings en la lista dada y N es la longitud de cada string.
Espacio auxiliar: O(M*N)