Find String in a Character Matrix

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Find String in a Character Matrix. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

A Smartsheet grid contains single-character cell values. Given a rectangular character matrix board and a target string word, determine whether the word can be formed from adjacent cells.

A word path may move up, down, left, or right. Diagonal movement is not allowed, and the same cell may not be used more than once in one path.

Formal Specification

Implement exist_word(board, word):

Input: board, a non-empty rectangular list of lists of one-character strings, and word, a non-empty string.
Output: Return True if some valid path spells word; otherwise, return False.
The search is case-sensitive.

Constraints

1 <= len(board), len(board[0]) <= 6
1 <= len(word) <= 15
Every row has the same number of columns
Each cell contains one character
The board and word contain only English letters

Function Signature

def exist_word(board, word):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output