Участник:Ковальков Антон М05-903б/Word Search

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/word-search/

Python3

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.foo(board, i, j, word, []):
                    return True
        return False
 
    def foo(self, board, i, j, word, path) -> bool:
        if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]):
            return False
        if board[i][j] != word[0]:
            return False
        if len(word) ==  1:
            return True
        for (n, m) in (-1, 0), (1, 0), (0, 1), (0, -1):
            if (i+n, j+m) in path:
                continue
            new_path = [x for x in path]
            new_path.append((i, j))
            if self.foo(board, i + n, j + m, word[1:], new_path):
                return True
        return False