動機

複習dfs

這次寫dfs的教訓

  1. 把會回傳true的放前面 (像是[["a"]])，不然明明已經成功卻因為邊界檢查而失敗
  2. 把所有失敗條件放到base case中，在寫的時候不知道是頭撞到了還是怎樣，明明沒有比對到字卻還是讓dfs繼續跑…

Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

 

Example 1:

Input: board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = ABCCEDOutput: true

Example 2:

Input: board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = SEEOutput: true

Example 3:

Input: board = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = ABCBOutput: false

 

Constraints:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board and word consists of only lowercase and uppercase English letters.

 

Follow up: Could you use search pruning to make your solution faster with a larger board?

Sol

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        vis = [[False for _ in x] for x in board]
        def dfs(w,k,i,j):
            if len(w) == k:
                return True
            elif i < 0 or j < 0 or j >= len(board[0]) or i >= len(board) or vis[i][j] or board[i][j] != w[k]:
                return False
            else:
                vis[i][j] = True
                ret = any([dfs(w,k+1,i+1,j),dfs(w,k+1,i,j+1),dfs(w,k+1,i-1,j),dfs(w,k+1,i,j-1)])
                vis[i][j] = False
                return ret
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(word,0,i,j):
                    return True
        return False