CareerCup

Hi,
I am not sure,but we can use BFS traversal to find the min no of steps.Where your source node would be HEAD and destination node would be TAIL,and at each level if a word doesn't belong to the dictionary we will remove it from the queue

sounds like it could be solved by generating a graph from the words in the dictionary where the source word is the root, the target word is one of the leaf nodes and the nodes in between are words of the same length, where there is an edge between word w1 and word w2 if there is exactly one char different between w1 and w2. Then just do dijkstra /shortest path on that graph.

If we already have dictionary implemented and saved with us, it should be in m-way Tries and HEAD should be one of the words. We just have to walk up the trie finding 4 letter words in the trie (since dictionary is implemented in trie so all words are valid words). so it could be like head->heal->heel->h#el no valid word like this then step back->heal->hell->hall->tall (target letter on 1st place reached)->tail {answer}
comments expected..

public static boolean isValid(String word)
  {
    Set<String> dict = new HashSet<String>();
    dict.add("cat");
    dict.add("car");
    dict.add("tar");
    dict.add("tor");
    dict.add("toy");
    dict.add("toz");
    if (dict.contains(word))
      return true;
    return false;
  }

  public static void main(String[] args)
  {
    System.out.println(minTransforms(Arrays.asList(0, 1, 2), "cat", 0, "toz",new HashSet<String>()));
  }

  public static int minTransforms(List<Integer> indxes, String word, int len, String dest,Set<String> visited)
  {
    if (word.equals(dest))
      return len;
    int lenT = Integer.MAX_VALUE;
    for (int i=0;i<word.length();i++)
    {
      if(word.charAt(i)==dest.charAt(i))continue;
      List<String> words = generateWords(i, word);
      List<Integer> ind = new ArrayList<>(indxes);
      for (String word_new: words)
      {
        if (!word_new.equals(word) && isValid(word_new) && !visited.contains(word_new))
        {
          //ind.remove(indx);
          visited.add(word_new);
          lenT = Math.min(minTransforms(ind, word_new, len + 1, dest,visited), lenT);
          visited.remove(word_new);
        }
      }
    }
    return lenT;
  }

  public static List<String> generateWords(int indx, String word)
  {
    List<String> words = new ArrayList<String>();
    char chr[] = word.toCharArray();
    for (char a = 'a'; a <= 'z'; a++)
    {
      chr[indx] = a;
      String str = new String(chr);
      words.add(str);
    }
    return words;
  }