Last Updated: 7 Feb, 2021
Count Strings
Moderate
Asked in company
Peter Parker (Spider-Man) want to time travel to save Tony Stark.
So Peter came to Doctor Strange for help. Doctor strange told Peter that he would help him if he can solve Strange’s problem. Peter accepts the challenge.
Doctor Strange gave Peter a grid having ‘N’ strings of size ‘M’ each. Then he gave Peter a string ‘S’. The task is to count the total number of paths in grid starting from any coordinate in the grid by moving only in left, right, up and down directions such that the string formed by characters in the path will be equal to ‘S’. Also, visiting a coordinate twice in a path is not allowed.
As Peter wants to bring Tony back as soon as possible, he called you for help.
The fate of Tony and Peter lies in your hand.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.
Each test case’s first line contains two space-separated integers ‘N’ and ‘M’. Here ‘N’ denotes the number of rows and ‘M’ represents the number of columns in the grid.
The next ‘N’ lines contain a single string of length ‘M’.
The next line contains a string ‘S’.
Output Format :
For each test case, print a single integer that denotes the total number of unique paths in the string.
The output of each test case will be printed in a separate line.
Constraints :
1 <= T <= 5
1 <= N, M <= 10
1 <= |S| <= N * M
Where ‘T’ is the number of test cases, ‘N’ denotes the number of rows and ‘M’ denotes the number of columns in the grid, and |S| denotes the length of string ‘S’.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Both ‘S’ and grid contain only uppercase English characters.
Approaches
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’.