上周一道算法题(六十)

又是上周，唉，题目难度级别'Medium'，使用语言'Python'，已经三周DFS算法了，可以搞个从入门到熟悉系列。。。

题目：给定一个二维网格和一个单词，找出该单词是否存在于网格中(返回true和false)。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。eg:board =[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']],给定 word = "ABCCED", 返回 true.给定 word = "SEE", 返回 true.给定 word = "ABCB", 返回 false.

思路：这题需要注意的就两点，第一是相邻的，第二是不可重复使用。于是思路就很简单了，先遍历找到word[0]，然后顺着起点开始找相邻的即可，最多就四个方向，上下左右，这里只需要注意是否使用过。下面看看代码

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        # 查看坐标是否可用
        def canUse(x, y, use):
            for i,j in use:
                if x == i and y == j:
                    return False
            return True
        # 深拷贝已使用坐标
        def copyUse(use):
            temp = []
            for x,y in use:
                temp.append((x, y))
            return temp
        # 搜索
        def search(row, col, i, word, board, row_len, col_len, wor_len, use):
            # 检查向下的点
            if row + 1 < row_len and canUse(row + 1, col, use):
                if word[i] == board[row+1][col]:
                    temp = copyUse(use)
                    temp.append((row + 1, col))
                    if wor_len > i+1:
                        if search(row+1, col, i+1, word, board, row_len, col_len, wor_len, temp):
                            return True
                    else:
                        return True
            # 检查向上的点
            if row - 1 >= 0 and canUse(row - 1, col, use):
                if word[i] == board[row-1][col]: 
                    temp = copyUse(use)
                    temp.append((row - 1, col))
                    if wor_len > i+1:
                        if search(row-1, col, i+1, word, board, row_len, col_len, wor_len, temp):
                            return True
                    else:
                        return True
            # 检查向右的点
            if col + 1 < col_len and canUse(row, col + 1, use):
                if word[i] == board[row][col+1]: 
                    temp = copyUse(use)
                    temp.append((row, col + 1))
                    if wor_len > i+1:
                        if search(row, col+1, i+1, word, board, row_len, col_len, wor_len, temp):
                            return True
                    else:
                        return True
            # 检查向左的点
            if col - 1 >= 0 and canUse(row, col - 1, use):
                if word[i] == board[row][col-1]: 
                    temp = copyUse(use)
                    temp.append((row, col - 1))
                    if wor_len > i+1:
                        if search(row, col-1, i+1, word, board, row_len, col_len, wor_len, temp):
                            return True
                    else:
                        return True
        # 从这里开始看
        # 记算board的行数，列数，及word的长度
        row_len = len(board)
        col_len = len(board[0])
        wor_len = len(word)
        # 剪枝，如果board里的元素比word的长度小，那就直接False
        if row_len * col_len < wor_len: 
            return False
        # 找起点（会有多个，所以找到一个也不能break）
        for x in range(0,row_len):
            for y in range(0, col_len):
                # 找到起点以后，如果word还没搜完，就从起点开始搜索
                if (board[x][y] == word[0]):
                    if wor_len > 1:
                        #参数分别是board的行数/列数/word字符的下标/word/board/board的总行数/总列数/word的总长度/已经使用过的坐标数组
                        if search(x, y, 1, word, board, row_len, col_len, wor_len, [(x,y)]):
                            return True
                    else:
                        return True
        return False

看这么长的代码就知道效率不怎么样了，我看了下效率高的，用了py的collections库，我还是先优化优化吧。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!