# Find Words
Name: Szu-Yu (Angela) Lin
Email: [e-mail]

## Introduction
The approach used to construct the solution is DFS (depth first search) and backtracking.

We have the following board layout, and we start the recursion from each cell in the grid.
For example, we start at the cell `[0, 1]`:

| | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | R | **A** | E | L |
| 1 | M | O | F | S |
| 2 | T | E | O | K |
| 3 | N | A | T | I |

And our current path string is `path = "A"`.

And during the DFS process, we expand in all 8 directions & mark visited cells with the character `#` so that we won't get caught in a loop forever.
For example, the visualization of the next step will look like this:

| | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | **R** | **#** | E | L |
| 1 | M | O | F | S |
| 2 | T | E | O | K |
| 3 | N | A | T | I |

And our path will be updated to `path = "AR"`

Since we have many directions to expand, we use backtracking to keep track of and update changes.

Once we find a word, for example, `path = "ARM"`,
we add it to our answer list if we haven't seen the same word before.
| | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | **#** | **#** | E | L |
| 1 | **M** | O | F | S |
| 2 | T | E | O | K |
| 3 | N | A | T | I |

## Optimization
First, we can terminate the searching process if the current path is already longer than the longest word in our dictionary.

In additional, to check whether a string is a valid word, or in other words, terminate the search if a string is not, the following is an approach:

> In English, the longest possible initial cluster is three consonants, as in split /ˈsplɪt/, strudel /ˈʃtruːdəl/, strengths /ˈstrɛŋkθs/.
> The most consecutive consonants in a word is six. This occurs in a number of words, the most familiar being catchphrase, sightscreen, and watchstrap.

As suggested, we can terminate the searching process if we have more than 6 consecutive consonants, or 3 consecutive initial consonants.

`if ((path.length() == 4 && counter == 4) || counter > 6 || (int)path.length() == max_len) return;`

## Reference
* https://en.wikipedia.org/wiki/Consonant_cluster
* https://blog.collinsdictionary.com/language-lovers/the-longest-word-in-the-collins-english-dictionary/