Given a 2D list of characters grid and a target string target_sequence, determine if target_sequence can be formed by sequentially adjacent cells in grid. Adjacent cells are horizontally or vertically neighboring. Each cell may be used at most once in forming the sequence. Return True if target_sequence exists in grid, otherwise return False.
Example 1
Input: grid = [[X,Y,Z],[A,B,C],[D,E,F]] target_sequence = XYZAB
Output: True
Explanation: The sequence XYZAB can be formed by moving right in the first row and then down to the second row.
Example 2
Input: grid = [[M,N,O],[P,Q,R],[S,T,U]] target_sequence = MNOPQ
Output: True
Explanation: The sequence MNOPQ can be formed by moving right in the first row and then down to the second row.
Example 3
Input: grid = [[L,M,N],[O,P,Q],[R,S,T]] target_sequence = LMNOPQRS
Output: False
Explanation: The sequence LMNOPQRS cannot be formed without reusing cells.
Constraints
Case 1
Input: grid = [['A','B'],['C','D']] target_sequence = 'ABCD'
Expected: False
Case 2
Input: grid = [['H','I','J'],['K','L','M'],['N','O','P']] target_sequence = 'HIJKL'
Expected: True
Case 3
Input: grid = [['Q','R','S'],['T','U','V'],['W','X','Y']] target_sequence = 'QRTUV'
Expected: True
Case 4
Input: grid = [['A','B','C'],['D','E','F'],['G','H','I']] target_sequence = 'AEI'
Expected: False
Case 5
Input: grid = [['Z','Y','X'],['W','V','U'],['T','S','R']] target_sequence = 'ZYXWVUTSR'
Expected: True