Word Morph

Interview

Time limit1sMemory limit128 MB

Summary

Given a dictionary of equal-length words, find the fewest one-letter changes needed to turn the start word into the end word through valid words.

Level: Medium5 of 10
Topics: BFS, Graph, Hash map, String
Solved: No attempts yet

Problem

Farmer John is playing a word game against his cows. It goes like this:

Farmer John first chooses a word, such as cat.
The cows then choose their own word, perhaps dog.

Farmer John must then morph his word into the cows' word. He does this by repeatedly changing a single letter at a time to form a new valid word, where a valid word is any word contained in the dictionary given in the input.

For example, Farmer John could build the following sequence of words:

cat -> cot -> cog -> dog

morphing cat into dog in just three changes. The cows will never set an impossible task, so a morph always exists. Farmer John must get from his word to the cows' word in as few changes as possible.

Given a starting word and an ending word, determine and output the least number of single-letter changes needed to morph the starting word into the ending word. Each change alters exactly one letter, and the resulting word must also be in the dictionary.

Input

Line 1: an integer $N$ , the number of words in the dictionary
Next $N$ lines: one dictionary word per line
Next line: the starting word
Next line: the ending word

Every word consists of lowercase letters only. The starting and ending words are guaranteed to be in the dictionary, and a morph from the starting word to the ending word is guaranteed to exist.

Output

Line 1: a single integer, the least number of single-letter changes required to transform the starting word into the ending word.

Examples3

Example 1
Input
```
4
cat
cot
cog
dog
cat
dog
```
Expected output
```
3
```
Example 2
Input
```
2
abc
abd
abc
abc
```
Expected output
```
0
```
Example 3
Input
```
2
hit
hot
hit
hot
```
Expected output
```
1
```