在一个二维矩阵中，每个元素都是一个字母，要判断目标字符串能否由该矩阵中的元素连接而成。所谓连接就是从矩阵中的某一个元素开始，向前后左右不断前进，但不允许再次经过走过的元素。

思路：dfs, 遍历二维列表，找到第一个字符所在的位置，然后调用dfs函数，测试当前位置的上下左右是否等于下一个字符，注意将当前位置先标记为#，避免重复遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        # 6 star, dfs
        def dfs(x, y, word):
            if not word:
                return True
            if x > 0 and board[x-1][y] == word[0]: # 向上
                temp = board[x][y]
                board[x][y] = "#"
                if dfs(x-1, y, word[1:]):
                    return True
                board[x][y] = temp
            if x < len(board) -1  and board[x+1][y] == word[0]: # 向下
                temp = board[x][y]
                board[x][y] = "#"
                if dfs(x+1, y, word[1:]):
                    return True
                board[x][y] = temp
            if y > 0 and board[x][y-1] == word[0]: # 向左
                temp = board[x][y]
                board[x][y] = "#"
                if dfs(x, y-1, word[1:]):
                    return True
                board[x][y] = temp
            if y < len(board[0]) - 1 and board[x][y+1] == word[0]: # 向右
                temp = board[x][y]
                board[x][y] = "#"
                if dfs(x, y+1, word[1:]):
                    return True
                board[x][y] = temp
            return False
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    if dfs(i, j, word[1:]):
                        return True
        return False