Two terms of the same length, “start” and “target,” are provided in a dictionary. Determine the length of the smallest chain, if any, between “start” and “target,” such that each word in the chain is a legitimate word—that is, it appears in the dictionary—and that adjacent words in the chain differ by no more than one character. It is reasonable to assume that the “target” term is present in a dictionary and that all dictionary words have the same length.
Example:
Input: Dictionary = {POON, PLEE, SAME, POIE, PLEA, PLIE, POIN}, start = TOON, target = PLEA
Output: 7
Explanation: TOON – POON – POIN – POIE – PLIE – PLEE – PLEAInput: Dictionary = {ABCD, EBAD, EBCD, XYZA}, start = ABCV, target = EBAD
Output: 4
Explanation: ABCV – ABCD – EBCD – EBAD
Approach: Using BFS is the suggested solution to the issue. Start with the start word and push it in a queue to determine the shortest path via BFS. Return that level of BFS traversal after the target is located for the first time. All of the phrases that can be created with that many stages are available in each BFS step. Thus, the length of the shortest word chain will be the first time the target word is discovered.
- Begin with the specified starting word.
- Add the word to the queue.
- Continue until the backlog is cleared.
- Push the word into a queue after traversing all words that are next to it (but differ by one character) (for BFS)
- Continue doing this until we reach the target word or have gone through every word.
- The aforementioned concept’s implementations are shown below.
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 PrinciRaj1992Python
# 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 29JS
<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>Output
Length of shortest chain is: 7
Time Complexity: O(N * M), where N is the number of entries originally in the dictionary and M is the size of the string.
Auxiliary Space: O(N+M)