Number of ways to form a string from a matrix of characters with the optimal approach in terms of time complexity?

Question

(UPDATED)

We need to find the number of ways a given string can be formed from a matrix of characters.

We can start forming the word from any position(i, j) in the matrix and can go in any unvisited direction from the 8 directions available across every cell(i, j) of the matrix, i.e

(i + 1, j)
(i + 1, j + 1)
(i + 1, j - 1)
(i - 1, j)
(i - 1, j + 1)
(i - 1, j - 1)
(i, j + 1)
(i, j - 1)

Sample test cases:

(1) input:

N = 3 (length of string) 
string = "fit"
matrix:   fitptoke   
          orliguek   
          ifefunef 
          tforitis

output: 7

(2) input:

N = 5 (length of string) 
string = "pifit"
matrix:   qiq
          tpf
          pip
          rpr

output: 5

Explanation:

num of ways to make 'fit' are as given below:

(0,0)(0,1)(0,2)
(2,1)(2,0)(3,0)
(2,3)(1,3)(0,4)
(3,1)(2,0)(3,0)
(2,3)(3,4)(3,5)
(2,7)(3,6)(3,5) 
(2,3)(1,3)(0,2)

I approach the solution as a naive way, go to every possible position (i,j) in the matrix and start forming the string from that cell (i, j) by performing DFS search on the matrix and add the number of ways to form the given string from that pos (i, j) to total_num_ways variable.

pseudocode:

W = 0
for i : 0 - n:
   for j: 0 - m:
        visited[n][m] = {false}
        W += DFS(i, j, 0, str, matrix, visited);

But it turns out that this solution would be exponential in time complexity as we are going to every possible n * m position and then traversing to every possible k(length of the string) length path to form the string.

How can we improve the solution efficiency?

Answer 1

Suggestion - 1: Preprocessing the matrix and the input string

We are only concerned about a cell of the matrix if the character in the cell appears anywhere in the input string. So, we aren't concerned about a cell containing the alphabet 'z' if our input string is 'fit'.

Using that, following is a suggestion.

1. Taking the input string, first put its characters in a set S. It is an O(k) step, where k is the length of the string;
2. Next we iterate over the matrix (a O(m*n) step) and:
   1. If the character in the cell does not appear in the S, we continue to the next one;
   2. If the character in the cell appears, we add an entry of cell position in a map of > called M.
3. Now, iterating over the input (not the matrix), for each position where current char c appears, get the unvisited positions of the right, left, above and below of the current cell;
4. If any of these positions are present in the list of cells in M where the next character is present in the matrix, then:
   1. Recursively go to the next character of the input string, until you have exhausted all the characters.

What is better in this solution? We are getting the next cell we need to explore in O(1) because it is already present in the map. As a result, the complexity is not exponential anymore, but it is actually O(c) where c is the total occurrences of the input string in the matrix.

---

Suggestion - 2: Dynamic Programming

DP helps in case where there is Optimal Substructure and Overlapping Subproblems. So, in situations where the same substring is a part of multiple solutions, using DP could help.

Ex: If we found 'fit' somewhere then if there is an 'f' in an adjacent cell, it could use the substring 'it' from the first 'fit' we found. This way we would prevent recursing down the rest of the string the moment we encounter a substring that was previously explored.

Answer 2

# Checking if the given (x,y) coordinates are within the boundaries
# of the matrix
def in_bounds(x, y, rows, cols):
    return x >= 0 and x < rows and y >= 0 and y < cols

# Finding all possible moves from the current (x,y) position
def possible_moves(position, path_set, rows, cols):
    moves = []
    move_range = [-1,0,1]
    for i in range(len(move_range)):
        for j in range(len(move_range)):
            x = position[0] + move_range[i]
            y = position[1] + move_range[j]
            if in_bounds(x,y,rows,cols):
                if x in path_set:
                    if y in path_set[x]:
                        continue
                moves.append((x,y))
    return moves

# Deterimine which of the possible moves lead to the next letter 
# of the goal string
def check_moves(goal_letter, candidates, search_space):
    moves = []
    for x, y in candidates:
        if search_space[x][y] == goal_letter:
            moves.append((x,y))
    return moves

# Recursively expanding the paths of each starting coordinate
def search(goal, path, search_space, path_set, rows, cols):
    # Base Case
    if goal == '':
        return [path]
    x = path[-1][0]
    y = path[-1][1]
    if x in path_set:
        path_set[x].add(y)
    else:
        path_set.update([(x,set([y]))])

    results = []
    moves = possible_moves(path[-1],path_set,rows,cols)
    moves = check_moves(goal[0],moves,search_space)

    for move in moves:
        result = search(goal[1:], path + [move], search_space, path_set, rows, cols)
        if result is not None:
            results += result
    return results

# Finding the coordinates in the matrix where the first letter from the goal
# string appears which is where all potential paths will begin from.
def find_paths(goal, search_space):
    results = []
    rows, cols = len(search_space), len(search_space[0])
    # Finding starting coordinates for candidate paths
    for i in range(len(search_space)):
        for j in range(len(search_space[i])):
            if search_space[i][j] == goal[0]:
                # Expanding path from root letter
                results += search(goal[1:],[(i,j)],search_space,dict(),rows,cols)
    return results

goal = "fit"
matrix = [
        'fitptoke',
        'orliguek',
        'ifefunef',
        'tforitis'
        ]

paths = find_paths(goal, matrix)
for path in paths:
    print(path)
print('# of paths:',len(paths))

Instead of expanding the paths from every coordinate of the matrix, the matrix can first be iterated over to find all the (i,j) coordinates that have the same letter as the first letter from the goal string. This takes O(n^2) time.

Then, for each (i,j) coordinate found which contained the first letter from the goal string, expand the paths from there by searching for the second letter from the goal string and expand only the paths that match the second letter. This action is repeated for each letter in the goal string to recursively find all valid paths from the starting coordinates.