M-79. Word Search

# 自己的解法
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def found_next(i, x, y, tested_matrix):
            if x >= len(board) or x < 0 or y >= len(board[0]) or y < 0 or tested_matrix[x][y] == 1:
                return False
            temp_char = tested_matrix[x][y] 
            tested_matrix[x][y] = 1
            if temp_char == word[i]:
                if len(word) == i+1: 
                    return True
                found = found_next(i+1, x, y+1, tested_matrix) or found_next(i+1, x+1, y, tested_matrix) or found_next(i+1, x, y-1, tested_matrix) or found_next(i+1, x-1, y, tested_matrix)
                if not found:
                    tested_matrix[x][y] = temp_char
                return found
            else:
                tested_matrix[x][y] = temp_char
                return False
        
        if not board: 
            return False

        for x in range(len(board)):
            for y in range(len(board[0])):
                tested_matrix = board.copy()
                if found_next(0, x, y, tested_matrix) == True:
                    return True
        return False
        
# 看了答案之后的稍微改进
cclass Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def found_next(i, x, y, tested_matrix):
            if x >= len(board) or x < 0 or y >= len(board[0]) or y < 0 or tested_matrix[x][y] != word[i]:
                return False
            temp_char = tested_matrix[x][y] 
            tested_matrix[x][y] = 1
            if len(word) == i+1: 
                return True
            found = found_next(i+1, x, y+1, tested_matrix) or found_next(i+1, x+1, y, tested_matrix) or found_next(i+1, x, y-1, tested_matrix) or found_next(i+1, x-1, y, tested_matrix)
            if not found:
                tested_matrix[x][y] = temp_char
            return found
        
        if not board: 
            return False

        for x in range(len(board)):
            for y in range(len(board[0])):
                tested_matrix = board.copy()
                if found_next(0, x, y, tested_matrix) == True:
                    return True
        return False

# 二次改进
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def found_next(i, x, y):
            if x >= len(board) or x < 0 or y >= len(board[0]) or y < 0 or board[x][y] != word[i]:
                return False
            if len(word) == i+1: 
                return True
            board[x][y] = "#"
            found = found_next(i+1, x, y+1) or found_next(i+1, x+1, y) or found_next(i+1, x, y-1) or found_next(i+1, x-1, y)
            board[x][y] = word[i]
            return found
        
        if not board: 
            return False

        for x in range(len(board)):
            for y in range(len(board[0])):
                if found_next(0, x, y):
                    return True
        return False

# 隔了一天之后写的：
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        directions = [(-1,0),(1,0),(0,1),(0,-1)]
        
        def dfs(x, y, i):
            if i==len(word):
                return True
            if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or board[x][y]!=word[i]:
                return False
            if board[x][y] == word[i]: # 这一行其实是默认的,可以略去
                board[x][y] = "#"
                for direction in directions:
                    found = dfs(x+direction[0], y+direction[1], i+1)
                    if found:
                        break
                board[x][y] = word[i]
            return found
        
        for x in range(len(board)):
            for y in range(len(board[0])):
                if dfs(x, y, 0):
                    return True
                
        return False

# 对上面的改进：
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        directions = [(-1,0),(1,0),(0,1),(0,-1)]
        
        def dfs(x, y, i):
        # 我们可以选择用A退出或者B退出
            ####### A ########
            if i==len(word):
                return True
            ####### A ########
            if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or board[x][y]!=word[i]:
                return False
            # 执行到这里，说明board[x][y]已经等于word[i]了
            ####### B ########
            if i==len(word)-1:
                return True
            ####### B ########
            board[x][y] = "#"
            for direction in directions:
                found = dfs(x+direction[0], y+direction[1], i+1)
                if found:
                    break
            board[x][y] = word[i]
            return found
        
        for x in range(len(board)):
            for y in range(len(board[0])):
                if dfs(x, y, 0):
                    return True
                
        return False
        
# 官方解法1：
class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        self.ROWS = len(board)
        self.COLS = len(board[0])
        self.board = board

        for row in range(self.ROWS):
            for col in range(self.COLS):
                if self.backtrack(row, col, word):
                    return True

        # no match found after all exploration
        return False


    def backtrack(self, row, col, suffix):
        # bottom case: we find match for each letter in the word
        if len(suffix) == 0:
            return True

        # Check the current status, before jumping into backtracking
        if row < 0 or row == self.ROWS or col < 0 or col == self.COLS \
                or self.board[row][col] != suffix[0]:
            return False

        ret = False
        # mark the choice before exploring further.
        self.board[row][col] = '#'
        # explore the 4 neighbor directions
        for rowOffset, colOffset in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            ret = self.backtrack(row + rowOffset, col + colOffset, suffix[1:])
            # break instead of return directly to do some cleanup afterwards
            if ret: break

        # revert the change, a clean slate and no side-effect
        self.board[row][col] = suffix[0]

        # Tried all directions, and did not find any match
        return ret

#官方解法2

    def backtrack(self, row, col, suffix):
        """
            backtracking with side-effect,
               the matched letter in the board would be marked with "#".
        """
        # bottom case: we find match for each letter in the word
        if len(suffix) == 0:
            return True

        # Check the current status, before jumping into backtracking
        if row < 0 or row == self.ROWS or col < 0 or col == self.COLS \
                or self.board[row][col] != suffix[0]:
            return False

        # mark the choice before exploring further.
        self.board[row][col] = '#'
        # explore the 4 neighbor directions
        for rowOffset, colOffset in [(0, 1), (-1, 0), (0, -1), (1, 0)]:
            # sudden-death return, no cleanup.
            if self.backtrack(row + rowOffset, col + colOffset, suffix[1:]):
                return True

        # revert the marking
        self.board[row][col] = suffix[0]

        # Tried all directions, and did not find any match
        return False

# for debug 
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def found_next(i, x, y):
            print('i '+f'{i}')
            print('x '+f'{x}')
            print('y '+f'{y}')
            if len(word) == i: 
                print('2')
                print('==========')
                return True
            if x >= len(board) or x < 0 or y >= len(board[0]) or y < 0 or board[x][y] != word[i]:
                print('1')
                print('==========')
                return False
            
            print('==========')
            board[x][y] = "#"
            found = found_next(i+1, x, y+1) or found_next(i+1, x+1, y) or found_next(i+1, x, y-1) or found_next(i+1, x-1, y)
            board[x][y] = word[i]
            return found
        
        if not board: 
            return False

        for x in range(len(board)):
            for y in range(len(board[0])):
                if found_next(0, x, y):
                    return True
        return False