Detect subsequence in matrix

Question

Given a 2D matrix of characters and a string, determine if the string can be found as a subsequence in the matrix. A subsequence is defined as a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. The function should return true if the string can be formed as a subsequence from the matrix, and false otherwise.

Codemia · Accepted Answer

To determine if the given string can be found as a subsequence in the matrix, we can leverage a depth-first search (DFS) approach. A subsequence allows us to skip characters in the matrix, but the order of characters must be maintained. The DFS approach is suitable here as it allows us to explore all possible paths in the matrix to match each character of the string sequentially. Each cell in the matrix can be seen as a node in a graph, and from each node, we can explore its neighboring nodes (up, down, left, right) to find the next character of the string. 1. **Input Validation**: First, check if the matrix or string is empty. If either is empty, return false. 2. **DFS Function**: Implement a recursive DFS function that takes the current position in the matrix and the index of the current character in the string. 3. **Base Case**: If the current index equals the length of the string, it means we've successfully found all characters, so return true. 4. **Boundary Check**: Ensure that the current position is within bounds of the matrix and that the character at that position matches the current character of the string. 5. **Mark Visited**: Temporarily mark the cell as visited to avoid cycles, then recursively call DFS for all four possible directions (up, down, left, right). 6. **Backtrack**: After the DFS calls, unmark the cell to allow for other paths to explore. 7. **Start DFS**: Iterate through each cell in the matrix and initiate DFS if the cell matches the first character of the string. If any DFS call returns true, return true. 8. **Final Return**: If no paths lead to a valid subsequence, return false. Here is the Python implementation of the outlined approach: ```python def exists(matrix, string): if not matrix or not matrix[0] or not string: return False rows, cols = len(matrix), len(matrix[0]) visited = [[False] * cols for _ in range(rows)] def dfs(r, c, index): if index == len(string): return True if r < 0 or r >= rows or c < 0 or c >= cols: return False if visited[r][c] or matrix[r][c] != string[index]: return False visited[r][c] = True found = (dfs(r + 1, c, index + 1) or dfs(r - 1, c, index + 1) or dfs(r, c + 1, index + 1) or dfs(r, c - 1, index + 1)) visited[r][c] = False return found for r in range(rows): for c in range(cols): if matrix[r][c] == string[0]: if dfs(r, c, 0): return True return False ``` The time complexity of this solution is O(M * N * L) where M is the number of rows, N is the number of columns in the matrix, and L is the length of the string. This is because in the worst case, we may visit each cell and explore all possible characters recursively. The space complexity is O(M * N) due to the visited matrix that tracks the state of each cell during the DFS. 1. **Empty Matrix**: If the matrix is empty, return false immediately. 2. **Empty String**: If the string is empty, return true since an empty string is trivially a subsequence. 3. **Single Cell Matrix**: If the matrix has a single cell, check if that cell matches the string. 4. **String Longer than Total Characters**: If the string is longer than the total number of characters in the matrix, return false. 5. **Characters Not Present**: If any character in the string cannot be found in the matrix, the function should return false.

Detect subsequence in matrix

Vercel

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Vercel Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string