算法题--寻找字符串是否可以由二维字母矩阵中连续相邻字母构成

image.png

0. 链接

题目链接

1. 题目

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Constraints:

board and word consists only of lowercase and uppercase English letters.
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

2. 思路1：回溯法

• 起点可能是任意一个位置，所以遍历矩阵每个位置, 试图把该位置作为起点, 判断是否能寻找到一条路径
• 对于每个位置，在深度优先搜索的过程
  • 选择: 依次选择当前位置的每个相邻位置
  • 深入搜索: 根据当前选择的位置, 继续探寻下一个位置, 直至搜索至word的最后一个位置, 仍然可以找到符合条件的board位置, 则返回True, 在任意一个位置word当前字符和当前board位置不等，则说明此选择不合理
  • 撤销选择
• 只要一个位置的检查结果返回True，就说明找到了一条合法路径。

3. 代码

# coding:utf8
from typing import List


class Solution:
    def check(self, board: List[List[str]], board_states: List[List[int]],
              i: int, j: int, word: str, k: int):
        if board[i][j] != word[k]:
            return False
        elif k == len(word) - 1:
            return True
        else:
            board_states[i][j] = True
            k += 1
            array = [(0, -1), (0, 1), (-1, 0), (1, 0)]
            for each in array:
                temp_i = i + each[0]
                temp_j = j + each[1]
                if 0 <= temp_i < len(board) \
                        and 0 <= temp_j < len(board[0]) \
                        and board_states[temp_i][temp_j] is False \
                        and board[temp_i][temp_j] == word[k]:
                    board_states[temp_i][temp_j] = True
                    result = self.check(board, board_states, temp_i, temp_j, word, k)
                    if result:
                        return True
                    board_states[temp_i][temp_j] = False
            return False

    def exist(self, board: List[List[str]], word: str) -> bool:
        for i in range(len(board)):
            for j in range(len(board[0])):
                board_states = [[False] * len(board[0]) for _ in range(len(board))]
                if self.check(board, board_states, i, j, word, 0):
                    return True

        return False


def my_test(solution: Solution, board: List[List[str]], word: str):
    print('board={}, word={} => output:{}'.format(board, word, solution.exist(board, word)))


solution = Solution()
my_test(solution, [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E'],
], 'ABCCED')
my_test(solution, [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E'],
], 'SEE')
my_test(solution, [
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E'],
], 'ABCB')
my_test(solution, [["a","a"]], "aaa")

输出结果

board=[['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], word=ABCCED => output:True
board=[['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], word=SEE => output:True
board=[['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], word=ABCB => output:False
board=[['a', 'a']], word=aaa => output:False

4. 结果

image.png