Word Ladder

Transform begin into end by changing one letter at a time; every intermediate word (and end itself) must be in the word list. begin does not need to be in the list. Find the number of words in the shortest transformation sequence, counting both begin and end — or 0 if it is impossible.

Example: hit → hot → dot → dog → cog has 5 words.

Input:

• line 1: begin end
• line 2: n
• next n lines: the word list (distinct words)

Output: the length of the shortest sequence, or 0.

Constraints: 1 ≤ word length ≤ 10, 1 ≤ n ≤ 5000, all words have the same length and use lowercase letters; begin ≠ end.

Think about it: words are nodes, one-letter changes are edges — the answer is a BFS distance. Generate neighbours by trying all 26 letters at every position and looking them up in a hash set (O(n · L · 26)), instead of comparing all pairs of words.