<p>步骤:</p>
<ol>
<li>找到与电路板匹配的第一个字符</li>
<li>找到匹配项后,使用<a href="https://en.wikipedia.org/wiki/Backtracking" rel="nofollow noreferrer">backtracking</a>执行<a href="https://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow noreferrer">DFS</a>,直到完全匹配单词或由于不匹配而耗尽搜索</李>
<li>如果在上述步骤中未找到完全匹配,则继续扫描电路板。(即,转到步骤1)查找与板上匹配的下一个字符</李>
<li>如果在步骤3中找到匹配项,则报告成功</李>
</ol>
<p>这个解决方案也适用于<code>NxM</code>板</p>
<pre class="lang-py prettyprint-override"><code>def is_within_bounds(row, col, row_dim, col_dim):
return row >= 0 and row < row_dim and col >= 0 and col < col_dim
def get_neighbors(row, col, row_dim, col_dim):
for r_offset in (-1, 0, 1):
for c_offset in (-1, 0, 1):
if r_offset == 0 and c_offset == 0:
continue
r_new = row + r_offset
c_new = col + c_offset
if is_within_bounds(r_new, c_new, row_dim, col_dim):
yield (r_new, c_new)
def is_word_found(board, word, row, col, visited):
if word[0] != board[row][col]:
return False
if len(word) == 1:
return True
for neighbor in get_neighbors(row, col, len(board), len(board[0])):
if neighbor not in visited:
visited.add(neighbor)
if is_word_found(board, word[1:], neighbor[0], neighbor[1], visited):
return True
visited.remove(neighbor)
return False
def find_word(board, word):
for row in range(len(board)):
for col in range(len(board[0])):
if word[0] != board[row][col]:
continue
if is_word_found(board, word, row, col, set()):
return True
return False
</code></pre>