Count Strings

The idea here is to use brute force. For each coordinate in the grid, we will count the total number of paths starting from this coordinate. 

Algorithm:

• Declare a variable to count the total number of paths having a value equal to ‘S’, say ‘answer’.
• Declare a direction array to traverse in all four directions, i.e. left, right, down and up.
• Declare a function ‘isValid’ to check whether coordinate (x, y) is out of bound or not, i.e. check if ‘x’ lies between 0 and ‘N – 1’ and ‘y’ lies between 0 and ‘M – 1’. Here ‘N’, ‘M’ denotes the number of rows and columns in grid respectively.
• Run two nested loops to traverse all coordinates in the grid.
• Declare a 2-D ‘visited’ array to keep track of visited coordinates in the grid and initialise all its elements with false.
• Let us denote current coordinate in the grid by (x, y). Call ‘countPaths’ function to get the total number of valid paths starting at coordinate (x, y) and add it to ‘answer’.
• Finally, return the ‘answer’.

Description of the ‘countPaths’ function:

This function will take 6 arguments: ‘curX’ and ‘curY’ to keep track of current coordinate in the grid, 2  D grid and the string ‘S’ given in the problem, ‘curIndex’ to keep track of current index-matched so far of string ‘S’ and a 2 – D ‘visited’ array to keep track of visited elements in the grid. 

int countPaths(curX, curY, grid,S, curIndex, visited)

• If curIndex >= length of string ‘S’ then return 1.
• If ‘S[curIndex]’  is not equal to ‘grid[curX][curY]’ then return 0 as all paths starting from this coordinate will be invalid.
• Declare a variable ‘count’ to count the total number of valid paths starting from ‘curX’, ‘curY’ having a value equal to ‘S’ and initialise it with zero.
• Traverse all four directional neighbours(up, down, left, right) of (curX, curY) using direction array.
• Let us denote the current neighbour of (curX, curY) by (x, y).
• If (x, y) is not out of bounds and we haven’t visited (x, y) then recursively call ‘countPath’ function by incrementing ‘curIndex’ by one and passing (x, y) and add the value return by this recursion in ‘count’.
• Return ‘count’.

O( (N * M) * (3 ^ (N * M) ), where ‘N’ is the number of rows and ‘M’ is the number of columns in the grid.

Here, ‘countPath’ function takes O( (3 ^ (N * M) ) time in the worst case when all characters of grid and string ‘S’ are same and length of ‘S’ is (N * M). In this case, every possible path will be a valid path. In each recursive call, we make three more recursive calls to visit the neighbours of the current coordinate. Note that we cannot go back to the previous coordinate from where we have reached the current coordinate so we will recursively visit only three neighbours of current coordinate. In the worst case, we need to visit O(N * M) so elements. So it will require O( 3 ^ (N * M ) ) time. Also, we call ‘countPath’ for all nodes of which are N * M. 

Hence, the overall time complexity will be O(N * M) * O( 3 ^ (N * M ) ) = O( (N * M) * (3 ^ (N * M) ).

O(N * M), where ‘N’ is the number of rows, and ‘M’ is the number of columns in the grid.

We are using a visited array that takes O(N * M) space. In the worst case, we need O(N * M) recursive calls which require O(N * M) stack space. 

Hence, the overall space complexity will be O(N * M) + O(N * M) = O(N * M).