Imprima todas las strings más cortas posibles para llegar a una palabra objetivo

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úplica

Entrada: 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:

1. Inicialice una variable, digamos res , para almacenar todas las rutas más cortas posibles.
2. 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.
3. 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.
4. Finalmente, imprime todas las rutas posibles.

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

# 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)