Day 27 LeetCode 212. Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must 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 in a word.

Example 1:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

from typing import List

class Solution:

    def dfs(self, board: List[List[str]], word: str, wordid: int, x:int, y:int ):
        if x < 0 or y < 0 or x >= len(board) or y >= len(board[0]):
            return False

        if not board[x][y]:
            return False

        if  wordid >= len(word):
            return False

        if board[x][y] != word[wordid]:
            return False
 
        if wordid == len(word) -1:
            return True

        temp = str(board[x][y])
        board[x][y] = " "
        if self.dfs(board, word, wordid+1, x+1, y) or self.dfs(board, word, wordid+1, x-1, y):
            board[x][y] = temp
            return True

        if self.dfs(board, word, wordid+1, x, y+1) or self.dfs(board, word, wordid+1, x, y-1):
            board[x][y] = temp
            return True
        board[x][y] = temp
        return False


    def checkin(self, board, word: str):
        myset = set()
        wset = set()
        for a in board:
            myset.update(a)
        wset.update([i for i in word])

        return len(myset & wset) == len(wset)

    def findWord(self, board: List[List[str]], word: str) -> List[str]:
        for x in range(len(board)):
            for y in range(len(board[0])):
                if self.dfs(board, word, 0, x, y):
                    return True
        return False

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        result = []
        for word in words:
            if not self.checkin(board, word):
                continue
            if self.findWord(board,word):
                result.append(word)
        return result
        pass

board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath","pea","eat","rain"]

print(Solution().findWords(board, words))

board = [["a","b"],["c","d"]]
words = ["abcb"]

print(Solution().findWords(board, words))

如果只是 DFS 肯定会超时，所以提前检查 board 里有没有 word 要的字，没的话就跳过这个案例。
这方法其实有点取巧...测资如果刁钻一点也不能过。