79 Word Search

[tech-cow]

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.

[tech-cow]

第一次刷

1. 常犯错：Parameter Passing的时候经常忘记加东西
2. 是len(board) 而不是 len(word)， 再有多个参考参数的时候，要注意分辨。。
3. 最好不要用slice

class Solution(object):
    def exist(self, board, word):
        if not board: return False   # No need
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfsHelper(board, i , j, word):
                    return True
        return False
    
    
    def dfsHelper(self, board, i, j, word):  # frequent bug: 经常没有match这个
        if len(word) == 0: return True
        
        if i < 0 or i >= len(word) or j < 0 or j >= len(word[0]) or word[0] != board[i][j]:  # bug wtf: len(word????)
            return False
        
        word = board[i][j]
        
        board[i][j] = '#'
        
        found = \
        self.dfsHelper(board, i - 1, j, word[1:]) or \    # Slicing是个Bad Idea，太多空间损耗，应该直接同index
        self.dfsHelper(board, i + 1, j, word[1:]) or \
        self.dfsHelper(board, i, j - 1, word[1:]) or \
        self.dfsHelper(board, i, j + 1, word[1:])
        
        board[i][j] = word
        return found

[tech-cow]

Working Code (使用Visited)

这里学到一招记录二维数组里面的Visited Elements: 这种方式消费了额外空间，但是不对原Input board进行修改。

时间复杂度

遍历所有的元素需要 m * n, 在每个元素使用一次DFS， 有4个方向(对应Recursion Tree里面的4个Branches，然后树的高度为k)

所以总共 O(m * n * 4^k)

class Solution(object):
    def exist(self, board, word):
        visited = {}
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfsHelper(board, i , j, visited, word, 0):
                    return True
        return False
                
                
    
    def dfsHelper(self, board, i , j, visited, word, wordIndex):
        '''
        rType: True/False -> Boolean
        '''
        
        if wordIndex == len(word):
            return True
        
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or word[wordIndex] != board[i][j] or visited.get((i, j)):
            return False
        
        visited[(i, j)] = True
        
        found = self.dfsHelper(board, i + 1, j, visited, word, wordIndex + 1) \
                or self.dfsHelper(board, i - 1, j, visited, word, wordIndex + 1) \
                or self.dfsHelper(board, i, j + 1, visited, word, wordIndex + 1) \
                or self.dfsHelper(board, i, j - 1, visited, word, wordIndex + 1)
        
        visited[(i, j)] = False
        return found

顺便用同一种方法肉了一圈LC 200

class Solution(object):
    def numIslands(self, grid):
        visited = {}
        res = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1' and not visited.get((i, j)):
                    self.dfsHelper(grid, i, j, visited)
                    res += 1  
        return res 
    
        
    def dfsHelper(self, grid, i, j, visited):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or visited.get((i, j)) or grid[i][j] != '1':
            return 
        
        visited[(i, j)] = True
        self.dfsHelper(grid, i + 1, j, visited)
        self.dfsHelper(grid, i - 1, j, visited)
        self.dfsHelper(grid, i, j + 1, visited)
        self.dfsHelper(grid, i, j - 1, visited)

[tech-cow]

Working Code (不使用Visited)

class Solution(object):
    def exist(self, board, word):
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.dfsHelper(board, i , j, word, 0):
                    return True
        return False
                
                
    
    def dfsHelper(self, board, i , j, word, wordIndex):
        if wordIndex == len(word):
            return True
        
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or word[wordIndex] != board[i][j]:
            return False
        
        board[i][j] = '#'
        
        found = self.dfsHelper(board, i + 1, j, word, wordIndex + 1) \
                or self.dfsHelper(board, i - 1, j, word, wordIndex + 1) \
                or self.dfsHelper(board, i, j + 1, word, wordIndex + 1) \
                or self.dfsHelper(board, i, j - 1, word, wordIndex + 1)
        
        board[i][j] = word[wordIndex]
        return found