Constrained Word Ladder

Graph Algorithm Bfs

In this problem, you are given two words, beginWord and endWord, along with a list of valid words called the dictionary. Your task is to determine the length of the shortest transformation sequence from beginWord to endWord under the following conditions:

  1. Only one letter can be changed in each step.
  2. Every intermediate word in the sequence must exist in the dictionary.
  3. Modification Constraint: When changing a letter, you can only replace a vowel with another vowel (vowels are: a, e, i, o, u) or a consonant with another consonant.

For example, if you have the word cat, the letter c (a consonant) can only be changed to another consonant (e.g., b, d, etc.), not to a vowel.

Input Parameters:

  • beginWord: The starting word.
  • endWord: The target word.
  • dictionary: A list of unique words, all of the same length.

Output:

  • Return the length of the shortest transformation sequence, including the beginWord and endWord. If no such sequence exists, return 0.

Example:

Input:
  beginWord = "lead"
  endWord = "gold"
  dictionary = ["load", "goad", "gold", "lead", "toad"]

Output:
  4

Explanation:
One valid transformation sequence is: "lead" -> "load" -> "goad" -> "gold".
Each transformation complies with the rule that a vowel is replaced by a vowel or a consonant by a consonant.

Additional Notes:

  • All words have the same length.
  • The dictionary does not contain duplicate words.
  • The beginWord and endWord are guaranteed to be non-empty and different.

Implement a function or method in your preferred programming language that solves this problem efficiently, keeping in mind that the dictionary can be large.