# Graph 1, Word Ladders II

### Problem Statement

A word ladder is a sequence of words in which each word can be transformed into the next word by changing one letter. For example, the word ladder below changes 'lot' to 'log'.
```   lot dot dog log
```
This is not the shortest word-ladder between 'lot' and 'log' since the former can be immediately changed to the latter yielding a word ladder of length two:
```  lot log
```
The first and last words in a word ladder are the anchor rungs of the ladder. Any other words are interior rungs. For example, there are three interior rungs in the ladder below between 'smile' and 'evote'.
```   smile smite smote emote evote
```
In this problem you'll write a method that has parameters representing potential interior rungs: a vector of strings (these by nonsense or English words), and the anchor rungs --- two strings. Your code must determine the shortest word ladder between the anchor rungs that uses at least one interior rung, and the number of such ladders. Return a vector containing two ints: the first is the length of the shortest valid word ladder and the second is the number of shortest ladders. If there are no valid ladders return [0,0].

### Definition

• Method: solve
• Parameters: `const tvector<string>& ` `const string&`, `const string&`
• Returns: ` tvector<int>`
• Method signature:
```   tvector<int> solve(const tvector<string>& words,
const string& from, const string& to);
```
(be sure your method is public)

### Class

class WordLadder { public: tvector<int> solve(const tvector<string>& words, const string& from, const string& to) { // fill in code here } };

### Notes

The parameters from and to are the anchor rungs, they must be connected by at least one interior rung from words or there are no valid word ladders.

### Constraints

• words contains at most 50 words.

• All strings contain only lowercase, alphabetic characters.

• All strings in word are the same length and are the same length as from and to.

### Examples

1. ```[hot, dot, dog] hit cog
```
Returns [5, 1]

The only ladder is hit hot dot dog cog which has length five.

2. ```[hot, dot, dog, lot, log] hit cog
```
Returns [5, 2]

Now there are two length-five ladders:

```  hit hot dot dog cog
hit hot lot log cog
```
3. ```[rain, ruin, gain, grin, grit, main, pain, pair, pail, mail] sail ruip
```
Returns: [6, 2]

```  sail mail main rain ruin ruip
sail pail pain rain ruin ruip
```

4. ```[most, mist, fist, fish,] lost cost
```
Returns [3, 1]

Although lost is directly connected to cost, a valid word ladder must contain an interior rung so the shortest ladder is

```   lost most cost
```
5. ```[mist, fist, fish,] lost cost
```
Returns [0, 0]

Although lost is directly connected to cost, a valid word ladder must contain an interior rung, there is no such ladder.

Owen L. Astrachan