Question

Design an algorithm which transforms a source word to a target word. for example: from head to tail. In each step, you just can replace one character, and the resulting word must be valid. You'll be given a dictionary. Your function must not only return if there is a path but spell the specific path: bool isThereValidPath(map validWords, string startWord, string endWord) {}

Program should be in java

Answer 1

Solution :

Logic:

BFS can solve this problem .start with source word and check all words(to given dictionary) that adjacent (differ by one character) to current word and keep repeating this , until we find the word as target word.

// sample Input:

String[] words = {"poon","plee","same","poie","plie","poin","plea"}; // given dictionary word

        String source = "toon"; // source word
       String target = "plea"; // target word

//output :

true
Path follows..
[toon, poon, poin, poie, plie, plee, plea]

// If you have any doubt ,feel free to ask, Thank you .

import java.util.*;
import java.util.Map.Entry;

public class SourceToTarget {
  
   static ArrayList path = new ArrayList();

   static //To check if strings differ by exactly one character
   boolean checkDifference(String first, String second)
   {
       int count = 0; // to store count of differences
       int n = first.length();
      
       char[] firstArray = first.toCharArray();
       char[] secondArray = second.toCharArray();
      

       // Iterate through all characters and return false
       // if there are more than one mismatching characters
       for (int i = 0; i < n; i++)
       {
           if (firstArray[i] != secondArray[i]) {
               count++;
           }
           if (count > 1) {
               return false;
           }
       }
       return count == 1 ? true : false;
   }

   static boolean isThereValidPath(HashMap validWords, String source, String target) {
      
       // Create a queue for BFS and insert 'start' as source vertex
       Queue<String> queue = new LinkedList();
       queue.add(source);
       path.add(source);
       while(!queue.isEmpty()) {
          
           String current = queue.remove();
           Set<Entry<String,Integer>> entrySet = validWords.entrySet();
           Iterator<Entry<String,Integer>> itr = entrySet.iterator();
          
                while(itr.hasNext()) {
                  
                    Entry<String,Integer> entry = (Entry<String, Integer>) itr.next();
                    String key = entry.getKey();
                   if (checkDifference(current, key))
                   {
                       // Add the dictionary word to Q
                      
                      
                       String temp = key;
                       if(validWords.get(temp).equals(1)) {
                           path.add(key);
                           queue.add(key);
                           // Remove from dictionary so that this word is not
                           // processed again. This is like marking visited
                          
                           validWords.put(temp,0); // marking as visited
                           // If we reached target
                           if (temp.equals(target)) {
                              
                               return true;
                           }
                       }
                   }
                }

       }

       return false;  
   }

   public static void main(String[] args) {
       // TODO Auto-generated method stub
      
       // given words
       String[] words = {"poon","plee","same","poie","plie","poin","plea"};
      
       HashMap<String,Integer> validWords = new HashMap<String,Integer>();
       for(String w : words) {
           validWords.put(w,1);
       }

       String source = "toon";
       String target = "plea";
       System.out.println(isThereValidPath( validWords, source, target));
      
       System.out.println("Path follows..");
       System.out.println(path);

   }

}