WordPattern

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.