Dado un diccionario y dos palabras ‘inicio’ y ‘objetivo’ (ambas de la misma longitud). Encuentre la longitud de la string más pequeña desde ‘inicio’ hasta ‘objetivo’ 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 la longitud de todas las palabras del diccionario es la misma.
Ejemplo:
C++
// C++ program to find length
// of the shortest chain
// transformation from source
// to target
#include <bits/stdc++.h>
using namespace std;
// Returns length of shortest chain
// to reach 'target' from 'start'
// using minimum number of adjacent
// moves. D is dictionary
int shortestChainLen(
string start, string target,
set<string>& D)
{
if(start == target)
return 0;
// If the target string is not
// present in the dictionary
if (D.find(target) == D.end())
return 0;
// To store the current chain length
// and the length of the words
int level = 0, wordlength = start.size();
// Push the starting word into the queue
queue<string> Q;
Q.push(start);
// While the queue is non-empty
while (!Q.empty()) {
// Increment the chain length
++level;
// Current size of the queue
int sizeofQ = Q.size();
// Since the queue is being updated while
// it is being traversed so only the
// elements which were already present
// in the queue before the start of this
// loop will be traversed for now
for (int i = 0; i < sizeofQ; ++i) {
// Remove the first word from the queue
string word = Q.front();
Q.pop();
// For every character of the word
for (int pos = 0; pos < wordlength; ++pos) {
// Retain the original character
// at the current position
char orig_char = word[pos];
// Replace the current character with
// every possible lowercase alphabet
for (char c = 'a'; c <= 'z'; ++c) {
word[pos] = c;
// If the new word is equal
// to the target word
if (word == target)
return level + 1;
// Remove the word from the set
// if it is found in it
if (D.find(word) == D.end())
continue;
D.erase(word);
// And push the newly generated word
// which will be a part of the chain
Q.push(word);
}
// Restore the original character
// at the current position
word[pos] = orig_char;
}
}
}
return 0;
}
// Driver program
int main()
{
// make dictionary
set<string> D;
D.insert("poon");
D.insert("plee");
D.insert("same");
D.insert("poie");
D.insert("plie");
D.insert("poin");
D.insert("plea");
string start = "toon";
string target = "plea";
cout << "Length of shortest chain is: "
<< shortestChainLen(start, target, D);
return 0;
}
Java
// Java program to find length
// of the shortest chain
// transformation from source
// to target
import java.util.*;
class GFG
{
// Returns length of shortest chain
// to reach 'target' from 'start'
// using minimum number of adjacent moves.
// D is dictionary
static int shortestChainLen(String start,
String target,
Set<String> D)
{
if(start == target)
return 0;
// If the target String is not
// present in the dictionary
if (!D.contains(target))
return 0;
// To store the current chain length
// and the length of the words
int level = 0, wordlength = start.length();
// Push the starting word into the queue
Queue<String> Q = new LinkedList<>();
Q.add(start);
// While the queue is non-empty
while (!Q.isEmpty())
{
// Increment the chain length
++level;
// Current size of the queue
int sizeofQ = Q.size();
// Since the queue is being updated while
// it is being traversed so only the
// elements which were already present
// in the queue before the start of this
// loop will be traversed for now
for (int i = 0; i < sizeofQ; ++i)
{
// Remove the first word from the queue
char []word = Q.peek().toCharArray();
Q.remove();
// For every character of the word
for (int pos = 0; pos < wordlength; ++pos)
{
// Retain the original character
// at the current position
char orig_char = word[pos];
// Replace the current character with
// every possible lowercase alphabet
for (char c = 'a'; c <= 'z'; ++c)
{
word[pos] = c;
// If the new word is equal
// to the target word
if (String.valueOf(word).equals(target))
return level + 1;
// Remove the word from the set
// if it is found in it
if (!D.contains(String.valueOf(word)))
continue;
D.remove(String.valueOf(word));
// And push the newly generated word
// which will be a part of the chain
Q.add(String.valueOf(word));
}
// Restore the original character
// at the current position
word[pos] = orig_char;
}
}
}
return 0;
}
// Driver code
public static void main(String[] args)
{
// make dictionary
Set<String> D = new HashSet<String>();
D.add("poon");
D.add("plee");
D.add("same");
D.add("poie");
D.add("plie");
D.add("poin");
D.add("plea");
String start = "toon";
String target = "plea";
System.out.print("Length of shortest chain is: "
+ shortestChainLen(start, target, D));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find length of the
# shortest chain transformation from source
# to target
from collections import deque
# Returns length of shortest chain
# to reach 'target' from 'start'
# using minimum number of adjacent
# moves. D is dictionary
def shortestChainLen(start, target, D):
if start == target:
return 0
# If the target is not
# present in the dictionary
if target not in D:
return 0
# To store the current chain length
# and the length of the words
level, wordlength = 0, len(start)
# Push the starting word into the queue
Q = deque()
Q.append(start)
# While the queue is non-empty
while (len(Q) > 0):
# Increment the chain length
level += 1
# Current size of the queue
sizeofQ = len(Q)
# Since the queue is being updated while
# it is being traversed so only the
# elements which were already present
# in the queue before the start of this
# loop will be traversed for now
for i in range(sizeofQ):
# Remove the first word from the queue
word = [j for j in Q.popleft()]
#Q.pop()
# For every character of the word
for pos in range(wordlength):
# Retain the original character
# at the current position
orig_char = word[pos]
# Replace the current character with
# every possible lowercase alphabet
for c in range(ord('a'), ord('z')+1):
word[pos] = chr(c)
# If the new word is equal
# to the target word
if ("".join(word) == target):
return level + 1
# Remove the word from the set
# if it is found in it
if ("".join(word) not in D):
continue
del D["".join(word)]
# And push the newly generated word
# which will be a part of the chain
Q.append("".join(word))
# Restore the original character
# at the current position
word[pos] = orig_char
return 0
# Driver code
if __name__ == '__main__':
# Make dictionary
D = {}
D["poon"] = 1
D["plee"] = 1
D["same"] = 1
D["poie"] = 1
D["plie"] = 1
D["poin"] = 1
D["plea"] = 1
start = "toon"
target = "plea"
print("Length of shortest chain is: ",
shortestChainLen(start, target, D))
# This code is contributed by mohit kumar 29
C#
// C# program to find length of the shortest chain
// transformation from source to target
using System;
using System.Collections.Generic;
class GFG
{
// Returns length of shortest chain
// to reach 'target' from 'start'
// using minimum number of adjacent moves.
// D is dictionary
static int shortestChainLen(String start,
String target,
HashSet<String> D)
{
if(start == target)
return 0;
// If the target String is not
// present in the dictionary
if (!D.Contains(target))
return 0;
// To store the current chain length
// and the length of the words
int level = 0, wordlength = start.Length;
// Push the starting word into the queue
List<String> Q = new List<String>();
Q.Add(start);
// While the queue is non-empty
while (Q.Count != 0)
{
// Increment the chain length
++level;
// Current size of the queue
int sizeofQ = Q.Count;
// Since the queue is being updated while
// it is being traversed so only the
// elements which were already present
// in the queue before the start of this
// loop will be traversed for now
for (int i = 0; i < sizeofQ; ++i)
{
// Remove the first word from the queue
char []word = Q[0].ToCharArray();
Q.RemoveAt(0);
// For every character of the word
for (int pos = 0; pos < wordlength; ++pos)
{
// Retain the original character
// at the current position
char orig_char = word[pos];
// Replace the current character with
// every possible lowercase alphabet
for (char c = 'a'; c <= 'z'; ++c)
{
word[pos] = c;
// If the new word is equal
// to the target word
if (String.Join("", word).Equals(target))
return level + 1;
// Remove the word from the set
// if it is found in it
if (!D.Contains(String.Join("", word)))
continue;
D.Remove(String.Join("", word));
// And push the newly generated word
// which will be a part of the chain
Q.Add(String.Join("", word));
}
// Restore the original character
// at the current position
word[pos] = orig_char;
}
}
}
return 0;
}
// Driver code
public static void Main(String[] args)
{
// make dictionary
HashSet<String> D = new HashSet<String>();
D.Add("poon");
D.Add("plee");
D.Add("same");
D.Add("poie");
D.Add("plie");
D.Add("poin");
D.Add("plea");
String start = "toon";
String target = "plea";
Console.Write("Length of shortest chain is: "
+ shortestChainLen(start, target, D));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find length
// of the shortest chain
// transformation from source
// to target
// Returns length of shortest chain
// to reach 'target' from 'start'
// using minimum number of adjacent moves.
// D is dictionary
function shortestChainLen(start,target,D)
{
if(start == target)
return 0;
// If the target String is not
// present in the dictionary
if (!D.has(target))
return 0;
// To store the current chain length
// and the length of the words
let level = 0, wordlength = start.length;
// Push the starting word into the queue
let Q = [];
Q.push(start);
// While the queue is non-empty
while (Q.length != 0)
{
// Increment the chain length
++level;
// Current size of the queue
let sizeofQ = Q.length;
// Since the queue is being updated while
// it is being traversed so only the
// elements which were already present
// in the queue before the start of this
// loop will be traversed for now
for (let i = 0; i < sizeofQ; ++i)
{
// Remove the first word from the queue
let word = Q[0].split("");
Q.shift();
// For every character of the word
for (let pos = 0; pos < wordlength; ++pos)
{
// Retain the original character
// at the current position
let orig_char = word[pos];
// Replace the current character with
// every possible lowercase alphabet
for (let c = 'a'.charCodeAt(0); c <= 'z'.charCodeAt(0); ++c)
{
word[pos] = String.fromCharCode(c);
// If the new word is equal
// to the target word
if (word.join("") == target)
return level + 1;
// Remove the word from the set
// if it is found in it
if (!D.has(word.join("")))
continue;
D.delete(word.join(""));
// And push the newly generated word
// which will be a part of the chain
Q.push(word.join(""));
}
// Restore the original character
// at the current position
word[pos] = orig_char;
}
}
}
return 0;
}
// Driver code
// make dictionary
let D = new Set();
D.add("poon");
D.add("plee");
D.add("same");
D.add("poie");
D.add("plie");
D.add("poin");
D.add("plea");
let start = "toon";
let target = "plea";
document.write("Length of shortest chain is: "
+ shortestChainLen(start, target, D));
// This code is contributed by unknown2108
</script>
C++
// C++ program to find length
// of the shortest chain
// transformation from source
// to target
#include <bits/stdc++.h>
using namespace std;
// Returns length of shortest chain
// to reach 'target' from 'start'
// using minimum number of adjacent
// moves. D is dictionary
int shortestChainLen(
string start, string target,
set<string>& D)
{
if(start == target)
return 0;
// Map of intermediate words and
// the list of original words
map<string, vector<string>> umap;
// Find all the intermediate
// words for the start word
for(int i = 0; i < start.size(); i++)
{
string str = start.substr(0,i) + "*" +
start.substr(i+1);
umap[str].push_back(start);
}
// Find all the intermediate words for
// the words in the given Set
for(auto it = D.begin(); it != D.end(); it++)
{
string word = *it;
for(int j = 0; j < word.size(); j++)
{
string str = word.substr(0,j) + "*" +
word.substr(j+1);
umap[str].push_back(word);
}
}
// Perform BFS and push (word, distance)
queue<pair<string, int>> q;
map<string, int> visited;
q.push(make_pair(start,1));
visited[start] = 1;
// Traverse until queue is empty
while(!q.empty())
{
pair<string, int> p = q.front();
q.pop();
string word = p.first;
int dist = p.second;
// If target word is found
if(word == target)
{
return dist;
}
// Finding intermediate words for
// the word in front of queue
for(int i = 0; i < word.size(); i++)
{
string str = word.substr(0,i) + "*" +
word.substr(i+1);
vector<string> vect = umap[str];
for(int j = 0; j < vect.size(); j++)
{
// If the word is not visited
if(visited[vect[j]] == 0)
{
visited[vect[j]] = 1;
q.push(make_pair(vect[j], dist + 1));
}
}
}
}
return 0;
}
// Driver code
int main()
{
// Make dictionary
set<string> D;
D.insert("poon");
D.insert("plee");
D.insert("same");
D.insert("poie");
D.insert("plie");
D.insert("poin");
D.insert("plea");
string start = "toon";
string target = "plea";
cout << "Length of shortest chain is: "
<< shortestChainLen(start, target, D);
return 0;
}
Java
// Java program to find length
// of the shortest chain
// transformation from source
// to target
import java.util.*;
class GFG{
static class pair
{
String first;
int second;
public pair(String first, int second)
{
this.first = first;
this.second = second;
}
}
// Returns length of shortest chain
// to reach 'target' from 'start'
// using minimum number of adjacent
// moves. D is dictionary
static int shortestChainLen(
String start, String target,
HashSet<String> D)
{
if(start == target)
return 0;
// Map of intermediate words and
// the list of original words
Map<String, Vector<String>> umap = new HashMap<>();
// Find all the intermediate
// words for the start word
for(int i = 0; i < start.length(); i++)
{
String str = start.substring(0,i) + "*" +
start.substring(i+1);
Vector<String> s = umap.get(str);
if(s==null)
s = new Vector<String>();
s.add(start);
umap.put(str, s);
}
// Find all the intermediate words for
// the words in the given Set
for(String it : D)
{
String word = it;
for(int j = 0; j < word.length(); j++)
{
String str = word.substring(0, j) + "*" +
word.substring(j + 1);
Vector<String> s = umap.get(str);
if(s == null)
s = new Vector<String>();
s.add(word);
umap.put(str, s);
}
}
// Perform BFS and push (word, distance)
Queue<pair> q = new LinkedList<>();
Map<String, Integer> visited = new HashMap<String, Integer>();
q.add(new pair(start, 1));
visited.put(start, 1);
// Traverse until queue is empty
while(!q.isEmpty())
{
pair p = q.peek();
q.remove();
String word = p.first;
int dist = p.second;
// If target word is found
if(word == target)
{
return dist;
}
// Finding intermediate words for
// the word in front of queue
for(int i = 0; i < word.length(); i++)
{
String str = word.substring(0, i) + "*" +
word.substring(i + 1);
Vector<String> vect = umap.get(str);
for(int j = 0; j < vect.size(); j++)
{
// If the word is not visited
if(!visited.containsKey(vect.get(j)) )
{
visited.put(vect.get(j), 1);
q.add(new pair(vect.get(j), dist + 1));
}
}
}
}
return 0;
}
// Driver code
public static void main(String[] args)
{
// Make dictionary
HashSet<String> D = new HashSet<String>();
D.add("poon");
D.add("plee");
D.add("same");
D.add("poie");
D.add("plie");
D.add("poin");
D.add("plea");
String start = "toon";
String target = "plea";
System.out.print("Length of shortest chain is: "
+ shortestChainLen(start, target, D));
}
}
// This code is contributed by 29AjayKumar
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA