Word Ladder (Length of shortest chain to reach a target word)

Last Updated : 02 Mar, 2023

Given a dictionary, and two words ‘start’ and ‘target’ (both of same length). Find length of the smallest chain from ‘start’ to ‘target’ if it exists, such that adjacent words in the chain only differ by one character and each word in the chain is a valid word i.e., it exists in the dictionary. It may be assumed that the ‘target’ word exists in dictionary and length of all dictionary words is same.

Example:

Input: Dictionary = {POON, PLEE, SAME, POIE, PLEA, PLIE, POIN}, start = TOON, target = PLEA
Output: 7
Explanation: TOON – POON – POIN – POIE – PLIE – PLEE – PLEA

Input: Dictionary = {ABCD, EBAD, EBCD, XYZA}, start = ABCV, target = EBAD
Output: 4
Explanation: ABCV – ABCD – EBCD – EBAD

Approach: The idea to solve the problem is to use BFS. To find the shortest path through BFS, start from the start word and push it in a queue. And once the target is found for the first time, then return that level of BFS traversal. In each step of BFS one can get all the words that can be formed using that many steps. So whenever the target word is found for the first time that will be the length of the shortest chain of words.

Start from the given start word.
Push the word in the queue
Run a loop until the queue is empty
Traverse all words that adjacent (differ by one character) to it and push the word in a queue (for BFS)
Keep doing so until we find the target word or we have traversed all words.

Below are the implementations of the above idea.

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>

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(M * N)

Alternate Implementation: (Maintaining the mapping of the intermediate words and the original word):

Below is an alternative implementation to the above approach.

Here, in this approach, we find out all the intermediate words of the start word and the words in the given list of dictionary and maintain a map of the intermediate word and a vector of the original word (map<string, vector<string>>). For instance, for the word “POON”, the intermediate words are “*OON” , “P*ON”, “PO*N”, “POO*”. Then, we perform BFS traversal starting with the start word and push a pair of start word and the distance (pair(word, distance)) to the queue until we reach the target word. Then, the distance is our answer.

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.*;
 
public 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

Python3

from typing import List, Tuple, Set, Dict, Any, Union
 
def shortest_chain_len(start: str, target: str, D: Set[str]) -> int:
    if start == target:
        return 0
 
    # Dictionary of intermediate words and
    # the list of original words
    umap: Dict[str, List[str]] = {}
 
    # Initialize umap with empty lists
    for i in range(len(start)):
        intermediate_word = start[:i] + "*" + start[i+1:]
        umap[intermediate_word] = []
 
    # Find all the intermediate words for
    # the words in the given Set
    for word in D:
        for i in range(len(word)):
            intermediate_word = word[:i] + "*" + word[i+1:]
            if intermediate_word not in umap:
                umap[intermediate_word] = []
            umap[intermediate_word].append(word)
 
    # Perform BFS and push (word, distance)
    q = [(start, 1)]
    visited = {start: 1}
 
    # Traverse until queue is empty
    while q:
        word, dist = q.pop(0)
 
        # If target word is found
        if word == target:
            return dist
 
        # Finding intermediate words for
        # the word in front of queue
        for i in range(len(word)):
            intermediate_word = word[:i] + '*' + word[i+1:]
            vect = umap[intermediate_word]
            for k in range(len(vect)):
               
                # If the word is not visited
                if vect[k] not in visited:
                    visited[vect[k]] = 1
                    q.append((vect[k], dist + 1))
 
    return 0
 
# Test
 
# Make dictionary
D = {'poon', 'plee', 'same', 'poie', 'plie', 'poin', 'plea'}
start = "toon"
target = "plea"
print(f"Length of shortest chain is: {shortest_chain_len(start, target, D)}")
 
# This code is contributed by vikramshirsath177

C#

// C# program to find length 
// of the shortest chain
// transformation from source
// to target
using System;
using System.Collections.Generic;
using System.Linq;
 
namespace GFG {
  public class GFG {
    class pair {
      public string first;
      public 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
      Dictionary<string, List<string> > umap
        = new Dictionary<string, List<string> >();
 
      // 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);
 
        if (!umap.ContainsKey(str))
          umap[str] = new List<string>();
        umap[str].Add(start);
      }
 
      // Find all the intermediate words for 
      // the words in the given Set
      foreach(string it in D)
      {
        string word = it;
        for (int j = 0; j < word.Length; j++) {
          string str = word.Substring(0, j) + "*"
            + word.Substring(j + 1);
 
          if (!umap.ContainsKey(str))
            umap[str] = new List<string>();
          umap[str].Add(word);
        }
      }
 
      // Perform BFS and push (word, distance)
      Queue<pair> q = new Queue<pair>();
      Dictionary<string, int> visited
        = new Dictionary<string, int>();
 
      q.Enqueue(new pair(start, 1));
      visited[start] = 1;
 
      // Traverse until queue is empty
      while (q.Count != 0) {
        pair p = q.Peek();
        q.Dequeue();
 
        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);
 
          List<string> vect
            = umap.ContainsKey(str)
            ? umap[str]
            : new List<string>();
 
          foreach(string s in vect)
          {
            // If the word is not visited
            if (!visited.ContainsKey(s)) {
              visited[s] = 1;
              q.Enqueue(new pair(s, dist + 1));
            }
          }
        }
      }
 
      return 0;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
      // Make dictionary
      HashSet<string> D = new HashSet<string>() {
        "poon", "plee", "same", "poie", "plie", "poin",
        "plea"
        };
      string start = "toon";
      string target = "plea";
      Console.WriteLine(
        "Length of shortest chain is: "
        + shortestChainLen(start, target, D));
    }
  }
}
 
// This code is contributed by prajwal kandekar

Javascript

// Javascript program to find length of the shortest chain transformation 
//from source to target
 
      // program to implement queue data structure
 
      class Queue {
        constructor() {
          this.items = [];
        }
 
        // add element to the queue
        push(element) {
          return this.items.push(element);
        }
 
        // remove element from the queue
        pop() {
          if (this.items.length > 0) {
            return this.items.shift();
          }
        }
 
        // view the first element
        front() {
          return this.items[0];
        }
 
        // check if the queue is empty
        empty() {
          return this.items.length == 0;
        }
 
        // the size of the queue
        size() {
          return this.items.length;
        }
 
        // empty the queue
        clear() {
          this.items = [];
        }
      }
 
      // 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;
        }
 
        // Map of intermediate words and
        // the list of original words
        let umap = new Map();
 
        // Find all the intermediate
        // words for the start word
        for (let i = 0; i < start.length; i++) {
          let str = start.slice(0, i) + "*" + start.slice(i + 1);
 
          if (umap.get(str) === undefined) {
            umap.set(str, [start]);
          } else {
            let brr = umap.get(str);
            brr.push(start);
            umap.set(str, brr);
          }
        }
 
        // Find all the intermediate words for
        // the words in the given Set
        for (it of D.values()) {
          let word = it;
 
          for (let j = 0; j < word.length; j++) {
            let str = word.slice(0, j) + "*" + word.slice(j + 1);
 
            if (umap.get(str) === undefined) {
              umap.set(str, [word]);
            } else {
              let arr = umap.get(str);
              arr.push(word);
              umap.set(str, arr);
            }
          }
        }
 
        // Perform BFS and push (word, distance)
        let q = new Queue();
        let visited = new Map();
 
        q.push([start, 1]);
        visited.set(start, 1);
 
        // Traverse until queue is empty
        while (!q.empty()) {
          let p = q.front();
          q.pop();
 
          let word = p[0];
          let dist = p[1];
 
          // If target word is found
          if (word == target) {
            return dist;
          }
 
          // Finding intermediate words for
          // the word in front of queue
          for (let i = 0; i < word.length; i++) {
            let str = word.slice(0, i) + "*" + word.slice(i + 1);
 
            let vect = umap.get(str);
 
            for (let j = 0; j < vect.length; j++) {
              // If the word is not visited
 
              if (visited.get(vect[j]) === undefined) {
                visited.set(vect[j], 1);
                q.push([vect[j], dist + 1]);
              }
            }
          }
        }
 
        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";
      console.log(
        "Length of shortest chain is: " + shortestChainLen(start, target, D)
      );

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(M * N)

GeeksforGeeks

Improve

Previous Article

Euler Circuit in a Directed Graph

Find if an array of strings can be chained to form a circle | Set 1

Similar Reads

Print all possible shortest chains to reach a target word

Given two strings start and target(both of the same length) and a list of strings str[], the task is to print all possible smallest sequences starting from start to target if it exists, such that adjacent words in the sequence only differ by a single character and each word in the sequence is present in the given list. Note: It may be assumed that

Word Ladder - Set 2 ( Bi-directional BFS )

Given a dictionary, and two words start and target (both of the same length). Find length of the smallest chain from start to target if it exists, such that adjacent words in the chain only differ by one character and each word in the chain is a valid word i.e., it exists in the dictionary. It may be assumed that the target word exists in the dicti

Find the length of the longest possible word chain

Given an array of words where each word consists of lowercase English letters, wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB, the task is to return the length of the longest possible word chain with words chosen from the

Find Shortest Distance to Target Color

Given an array colors, in which there are three colors: 1, 2 and 3. You are also given some queries. Each query consists of two integers i and c, return the shortest distance between the given index i and the target color c. If there is no solution return -1. Examples: Input: colors = [1, 1, 2, 1, 3, 2, 2, 3, 3], queries = [[1, 3], [2, 2], [6, 1]]O

Minimum steps to reach target by a Knight | Set 2

Given a square chessboard of N x N size, the position of Knight and position of a target is given, the task is to find out the minimum steps a Knight will take to reach the target position. Examples : Input : (2, 4) - knight's position, (6, 4) - target cell Output : 2 Input : (4, 5) (1, 1) Output : 3 A BFS approach to solve the above problem has al

Minimize moves to reach a target point from origin by moving horizontally or diagonally in right direction

Given source (X1, Y1) as (0, 0) and a target (X2, Y2) on a 2-D plane. In one step, either of (X1+1, Y1+1) or (X1+1, Y1) can be visited from (X1, Y1). The task is to calculate the minimum moves required to reach the target using given moves. If the target can't be reached, print "-1". Examples: Input: X2 = 1, Y2 = 0Output: 1Explanation: Take 1 step

Count of all possible ways to reach a target by a Knight

Given two integers N, M denoting N×M chessboard, the task is to count the number of ways a knight can reach (N, M) starting from (0, 0). Since the answer can be very large, print the answer modulo 109+7. Example: Input: N =3, M= 3Output: 2Explanation: Two ways to reach (3, 3) form (0, 0) are as follows:(0, 0) ? (1, 2) ? (3, 3)(0, 0) ? (2, 1) ? (3,

Minimum number of sum and modulo operations using given numbers to reach target

Given a number N, an array arr[], and a target number K, the task is to find minimum number of moves to reach K by choosing any array element and changing N to (N + arr[i]) mod 100000 in each move. Examples: Input: N = 99880, K = 89, arr = {100, 3}Output: 5Explanation: Number "100" is used 2 times and the number "3" is pushed 3 times, resulting in

Minimum swaps such that at least K points reach target within T time

Given N points moving along the X axis to the right whose initial position and speed are given in two arrays X[] (sorted in increasing order) and V[]. If at any time a point with a higher speed reaches a slow moving point then they will both continue moving with the slower speed. The task is to find out the minimum number of swaps we can perform on

Check if the player can reach the target co-ordinates after performing given moves from origin

Given an array arr[] of size N describing N moves. A player standing at origin (0, 0). In the first move, the player can move either right or left by distance arr[1]. In the second move, the player can move up or down by distance arr[2], In the third move player can move left or right by distance arr[3], and so on till arr[N]. That is on odd moves

Article Tags :

Practice Tags :