Find String in a Character Matrix | Dataford Interview Questions

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 question is Find String in a Character Matrix. Start with the requirements in the Question tab.

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

Problem