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 by traversing adjacent cells (horizontally or vertically). Return true if the string exists as a subsequence, and false otherwise. The input consists of the matrix dimensions and the target string, while the output is a boolean value indicating the presence of the subsequence.

Codemia · Accepted Answer

The task is to determine if a given string can be found as a subsequence in a 2D matrix of characters by traversing adjacent cells (horizontally or vertically). This problem can be approached using Depth-First Search (DFS) because we need to explore all possible paths from each cell in the matrix that might lead to forming the target string. The adjacency constraint implies that we need to keep track of the current position and the characters matched so far, which aligns well with recursive exploration. 1. Loop through each cell in the matrix as a starting point. 2. For each cell, initiate a DFS if the character matches the first character of the target string. 3. In the DFS function, check if the current index of the target string matches the length of the string; if so, return True. 4. If not, mark the current cell as visited to avoid re-exploration. 5. Explore all four possible directions (up, down, left, right) recursively to find the next character in the string. 6. After exploring all paths from the current cell, unmark it as visited for other potential paths. 7. If no valid paths lead to forming the string, return False. **Example:** For a matrix: [['A', 'B', 'C'], ['D', 'E', 'F'], ['G', 'H', 'I']] and target string 'ABE', the search would start from 'A' at (0,0), then move to 'B' at (0,1), and finally to 'E' at (1,1) to successfully form the string. ```python def exists(matrix, target): if not matrix or not matrix[0] or not target: return False rows, cols = len(matrix), len(matrix[0]) def dfs(r, c, index): if index == len(target): return True if r < 0 or c < 0 or r >= rows or c >= cols or matrix[r][c] != target[index]: return False temp = matrix[r][c] matrix[r][c] = '#' # Mark as visited found = (dfs(r + 1, c, index + 1) or # Down dfs(r - 1, c, index + 1) or # Up dfs(r, c + 1, index + 1) or # Right dfs(r, c - 1, index + 1)) # Left matrix[r][c] = temp # Unmark return found for r in range(rows): for c in range(cols): if matrix[r][c] == target[0] and dfs(r, c, 0): return True return False ``` The time complexity is O(N * M * 4^L), where N is the number of rows, M is the number of columns, and L is the length of the target string. This is due to the fact that for each cell, we may potentially explore in four directions for each character of the target string. The space complexity is O(L) for the recursion stack in the worst case when the string is equal to the length of the matrix dimensions. 1. **Empty Matrix:** If the matrix is empty, return False. 2. **Empty Target String:** If the target string is empty, return True since an empty string is trivially a subsequence. 3. **Single Character Match:** If the matrix has a single cell that matches the target string, return True. 4. **No Valid Path:** If no path exists to form the string due to adjacency constraints, return False. Consider testing with matrices of different sizes and shapes (e.g., 1xN, Nx1) to ensure robustness.

Detect subsequence in matrix

PayPal

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

PayPal 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