wordSearch

Given an array of strings words, find the number of ways to type the targetword by jumping from letter to letter in the array.

You may start from any letter. To get to the next letter, you can jump in one of the following eight directions assuming that you’re currently at word i and letter j (both 1-based):

1. up (to the string i - 1 and letter j, if i > 1 and the (i - 1)th word has at least j letters);
2. down (to the string i + 1 and letter j, if i < words.length and the (i + 1)th word has at least j letters);
3. left (to the string i and letter j - 1, if j > 1);
4. right (to the string i and letter j + 1, if the ith word has more than jletters.
5. up and left;
6. up and right;
7. down and left;
8. down and right.

It’s possible to jump on the same letter twice, but not twice in a row.

Example

• For words = ["STARTS", "HANNAH", "XXXXXX", "WWNNWW", "WAWWAW", "HWWWHH"] and target = "HANNAH", the output should be WordSearch(words, target) = 6.
  
  Here’re all possible ways to type targetusing words: ,
  
  ,
  
  ,

Note: It is highly recommended to put the array of strings into a 2D array, where each index corresponds to a string of length 1.

Input/Output

• [execution time limit] 0.5 seconds

• [input] array.string words

  Array of strings. Note, that array is not guaranteed to be rectangular.
  It is guaranteed that each character in each word is an uppercase English letter.

  Constraints:
  2 ≤ words.length ≤ 10,
  2 ≤ words[i].length ≤ 65.

• [input] string target

  The word to be found within the words, a string of uppercase English letters.

  Constraints:
  3 ≤ target.length ≤ 9.

• [output] integer

  • The number of ways to type target using the given words.