每日算法题 - Word Search

Hi, here's your problem today. This problem was recently asked by Amazon:

You are given a 2D array of characters, and a target string. Return whether or not the word target word exists in the matrix. Unlike a standard word search, the word must be either going left-to-right, or top-to-bottom in the matrix.

Example:

[['F', 'A', 'C', 'I'],

 ['O', 'B', 'Q', 'P'],

 ['A', 'N', 'O', 'B'],

 ['M', 'A', 'S', 'S']]

Given this matrix, and the target word FOAM, you should return true, as it can be found going up-to-down in the first column.

Here's the function signature:

def word_search(matrix, word):

  # Fill this in.

  

matrix = [

  ['F', 'A', 'C', 'I'],

  ['O', 'B', 'Q', 'P'],

  ['A', 'N', 'O', 'B'],

  ['M', 'A', 'S', 'S']]

print word_search(matrix, 'FOAM')

# True