leetcode 79. 单词搜索 (python)-python黑洞网

本站消息

站长简介/公众号

出租广告位,需要合作请联系站长

343ueru

1055

文章

825312

访问

+关注

分类

暂无分类

日期归档

2023-05(2)

2023-06(3)

leetcode 79. 单词搜索 (python)

发布于2020-02-28 12:29 阅读(1135) 评论(0) 点赞(10) 收藏(3)

在这里插入图片描述
题解：
本题是一个遍历搜索问题，我们可以用回溯算法进行求解。

在本题中，我们需要对二维网格的每个单元格进行遍历来查找和word的匹配；
因此我们首先建立一个二层的循环来遍历每一个单元格；
代码如下：

class Solution:
    def exist(self, board, word):

        #设置数组中的元素只能被使用一次
        used = [[False] * len(board[0]) for i in range(len(board))]
        # print(used)


        for i in range(len(board)):
            for j in range(len(board[0])):

                if(self.dfs_search(board, i, j,word,0,len(word) - 1)):
                    return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14

同时，在网格内移动的时候，我们可以向四个方向进行移动查找和word中一个字母的匹配（实际中需要排除来到这个位置的方向，只有三个方向；但是这个需要我们写代码去排除，并且，每个元素进行查找时需要排除的方向不一样，因此在代码中我们依旧写四个方向）
代码如下：

    def dfs_search(self, board, x, y, word,index,length_word):

        if board[x][y] != word[0]:
            return False

        #递归终止条件
        if index == length_word:
            return True

        #四个方向进行遍历
        # print(x,y)
        # print(word[0])
        # print('index,',index)
        # print('word',len(word) - 1)
        # if board[x][y] == word[0]:

            # used[x][y] = True
        tmp = board[x][y]
        board[x][y] = 0


        #向下遍历
        if (x < len(board) - 1 and self.dfs_search(board, x + 1, y, word[1:],index + 1,length_word)) or \
            (y < len(board[0]) - 1 and self.dfs_search(board, x, y + 1, word[1:],index + 1,length_word)) or \
            (x > 0 and self.dfs_search(board, x - 1, y, word[1:], index + 1,length_word)) or \
            (y > 0 and self.dfs_search(board, x, y - 1, word[1:], index + 1,length_word)):

                    return True
        


        board[x][y] = tmp


        return False
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

在上述代码中我们进行了tmp = board[x][y]，board[x][y] = 0的操作，是为了防止重复访问，即在进入dfs递归后，如果是重复访问的，board[x][y] != word[0]，会立刻返回；我们这样操作减少了设置一个和board同样大小的访问数组，提高空间和时间复杂度；
同时如果在进行回溯的过程中，如果四个方向都没有找到，我们需要进行回溯，返回上一个递归，在返回上一个递归之前，我们需要进行状态还原，因此我们需要设置board[x][y] = tmp。
因为本题是找到一条匹配的路径之后即可返回true；因此，任何一个if条件为true；我们就立刻返回true; 经过层层递归返回，exist函数返回true；
只要遍历网格找到一条路径为true，函数就返回true；而遍历完所有的网格都为false，才返回false。

完整的代码：

class Solution:
    def exist(self, board, word):

        #设置数组中的元素只能被使用一次
        used = [[False] * len(board[0]) for i in range(len(board))]
        # print(used)


        for i in range(len(board)):
            for j in range(len(board[0])):

                if(self.dfs_search(board, i, j,word,0,len(word) - 1)):
                    return True
        return False





    def dfs_search(self, board, x, y, word,index,length_word):

        if board[x][y] != word[0]:
            return False

        #递归终止条件
        if index == length_word:
            return True

        #四个方向进行遍历
        # print(x,y)
        # print(word[0])
        # print('index,',index)
        # print('word',len(word) - 1)
        # if board[x][y] == word[0]:

            # used[x][y] = True
        tmp = board[x][y]
        board[x][y] = 0


        #向下遍历
        if (x < len(board) - 1 and self.dfs_search(board, x + 1, y, word[1:],index + 1,length_word)) or \
            (y < len(board[0]) - 1 and self.dfs_search(board, x, y + 1, word[1:],index + 1,length_word)) or \
            (x > 0 and self.dfs_search(board, x - 1, y, word[1:], index + 1,length_word)) or \
            (y > 0 and self.dfs_search(board, x, y - 1, word[1:], index + 1,length_word)):

                    return True
        


        board[x][y] = tmp


        return False
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
43
44
45
46
47
48
49
50
51
52
53
54

在这里插入图片描述
另外记录一下本题的AC过程：
首先采用的是比较容易想到的方法，设置了和board一样大小的数组，来记录每个单元格是否被访问；时间复杂度较高，但是容易理解：

class Solution:
    def exist(self, board, word):

        #设置数组中的元素只能被使用一次
        used = [[False] * len(board[0]) for i in range(len(board))]
        # print(used)


        for i in range(len(board)):
            for j in range(len(board[0])):

                if(self.dfs_search(board, i, j,word,0,len(word) - 1,[[False] * len(board[0]) for i in range(len(board))])):
                    return True
        return False





    def dfs_search(self, board, x, y, word,index,length_word,used):

        #递归终止条件
        if index == length_word and board[x][y] == word[0]:
            return True

        #四个方向进行遍历
        # print(x,y)
        # print(word[0])
        # print('index,',index)
        # print('word',len(word) - 1)
        if board[x][y] == word[0]:

            used[x][y] = True


            #向下遍历
            if x < len(board) - 1:
                if used[x + 1][y] == False:

                    if(self.dfs_search(board, x + 1, y, word[1:],index + 1,length_word,used)):

                        return True
                    # else:
                    #     #回溯过程中设置未访问
                    #     used[x][y] = False


            #向右遍历
            if y < len(board[0]) - 1:
                # print("###")
                # print(x,y+1)
                if used[x][y + 1] == False:

                    if(self.dfs_search(board, x, y + 1, word[1:],index + 1,length_word,used)):

                        return True
                    # else:

                    #     used[x][y] = False
            #向上遍历
            if x > 0:
                if used[x - 1][y] == False:

                    if(self.dfs_search(board, x - 1, y, word[1:], index + 1,length_word,used)):
                        return True

                    # else:

                    #     used[x][y] = False
            #向左遍历
            if y > 0:
                if used[x][y - 1] == False:
                    if(self.dfs_search(board, x, y - 1, word[1:], index + 1,length_word,used)):
                        return True

                    # else:

                    #     used[x][y] = False
            
            used[x][y] = False

            return False


        else:

            return False
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

在这里插入图片描述
之后看了题解，对自己的方法进行了优化，去掉了used数组；
代码如下：

class Solution:
    def exist(self, board, word):

        #设置数组中的元素只能被使用一次
        used = [[False] * len(board[0]) for i in range(len(board))]
        # print(used)


        for i in range(len(board)):
            for j in range(len(board[0])):

                if(self.dfs_search(board, i, j,word,0,len(word) - 1)):
                    return True
        return False





    def dfs_search(self, board, x, y, word,index,length_word):
        if board[x][y] != word[0]:
            return False

        #递归终止条件
        if index == length_word:
            return True

        #四个方向进行遍历
        # print(x,y)
        #print(word[0])
        #print('index,',index)
        #print('word',len(word) - 1)
        # if board[x][y] == word[0]:

            # used[x][y] = True
        tmp = board[x][y]
        board[x][y] = 0


        #向下遍历
        if x < len(board) - 1:
            # if used[x + 1][y] == False:

                if(self.dfs_search(board, x + 1, y, word[1:],index + 1,length_word)):

                    return True
                # else:
                #     #回溯过程中设置未访问
                #     used[x][y] = False


        #向右遍历
        if y < len(board[0]) - 1:
            # print("###")
            # print(x,y+1)
            # if used[x][y + 1] == False:

                if(self.dfs_search(board, x, y + 1, word[1:],index + 1,length_word)):

                    return True
                # else:

                #     used[x][y] = False
        #向上遍历
        if x > 0:
            # if used[x - 1][y] == False:

                if(self.dfs_search(board, x - 1, y, word[1:], index + 1,length_word)):
                    return True

                # else:

                #     used[x][y] = False
        #向左遍历
        if y > 0:
            # if used[x][y - 1] == False:
                if(self.dfs_search(board, x, y - 1, word[1:], index + 1,length_word)):
                    return True

                # else:

                #     used[x][y] = False

        board[x][y] = tmp


        return False
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87