One day, I started writing out the following patterns (The procedure for constructing the pattern is deliberately not given, you must infer the procedure through the examples):
Input string: "HELLO" (quotes for clarity only)
Pattern: O
OLO
OLLLO
OLLELLO
OLLEHELLO
OLLELLO
OLLLO
OLO
O
Input string: "TC" (quotes for clarity only)
Pattern: C
CTC
C
Input string: "ABCD" (quotes for clarity only)
Pattern: D
DCD
DCBCD
DCBABCD
DCBCD
DCD
D
After constructing the patterns, I noticed something interesting. Starting with the first letter of the input string (which appears only once in the very center of the pattern), I can trace a path outwards toward the edges, spelling out the original input string. Of course, I only move Up, Down, Left and Right from any letter. I'm now perplexed because I want to know how many ways the original input string can be spelled out in the pattern. I must always end at an edge, and I can't go over one letter more than once while spelling a word.
Create a class WordPattern containing the method countWords which takes a String word as input. The method should return a long which is the number of ways the original input can be spelled out in the pattern according to my rules. |