NewThe Learning module is now liveSee what's new

You are given a 2D character matrix matrix with m rows and n columns, and a string s. Count the number of (starting cell, direction) pairs from which reading consecutive characters along the matrix produces s.

A match is counted when, for some starting cell (r, c) and one of the three allowed directions, every cell along the path stays within the matrix and the characters along the path equal s in order. The three allowed directions, given as one step (row-step, column-step), are:

  1. Horizontal (right): step (0, +1)
  2. Vertical (down): step (+1, 0)
Test Cases
Input
Output
Expected