### PROBLEM LINK:

**Author:** Anudeep Nekkanti

**Tester:** Mahbubul Hasan

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Easy

### PREREQUISITES:

Directed Graph, Floyd Algorithm

### PROBLEM:

There are **M** mappings from lower case English alphabet to lower case English alphabet. Using these mappings, can one transform a string **S** to another string **T**?

### EXPLANATION:

Let **Can[i][j]** denote whether the lower case English character **i** could be transformed to **j** in some combinations of given mappings. Initially, only **Can[i][i]** and the given mappings are set to true.

Then, the Floyd algorithm used to compute the transiting property can be adopted here, as the following:

```
For k = 1 to 26:
For i = 1 to 26:
For j = 1 t 26:
Can[i][j] |= Can[i][k] && Can[k][j]
```

After that, we have known all possible transformations between lower case characters. To answer the question, we just need to check the reachability between corresponding characters of the two strings **S** and **T**.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Solutions will be available soon.

Author’s solution can be found here.

Tester’s solution can be found here.