Leetcode 79: Word Search not understanding test case

Question

I'm trying to solve word search. I've pasted over the question.

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.

I have the code below which works for some test cases.

def exist(self, board: List[List[str]], word: str) -> bool:
        M, N = len(board), len(board[0])
        def search(r, c, word):
            if r < 0 or r >= M or c < 0 or c >= N or board[r][c] != word[0]:
                return False
            if len(word) == 1 and board[r][c] == word:
                return True
            if board[r][c] == word[0]:
                board[r][c] = '.'
                if search(r+1, c, word[1:]) or search(r-1, c, word[1:]) or search(r, c+1, word[1:]) or search(r, c-1, word[1:]):
                    return True
                
        for r in range(M):
            for c in range(N):
                if search(r, c, word):
                    return True
        return False

It fails for the test case where the matrix is

[["C","A","A"],
 ["A","A","A"],
 ["B","C","D"]]

and the target word is AAB. However the problem statement says "The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring." In this case isn't the B a diagonal neighbor of the second A so I don't understand why it should return true.

Answer 1

The point Marat is trying to make is that in the first illustration The word the challenge is asking for you to find is "ABCCED" and as you can see in the image, it is permited to mix vertical and horizontal moves in any direction in order to find that word.

So for your example the a correct solution would be this order of steps:

   A      A      B
[(1,1), (1,0), (2,0)]

I wrote this solution to the problem... it isn't the prettiest but it was accepted.

class Solution:
        
    def issafe(self,x,y):
        if x < self.height and x >= 0:
            if y < self.width and y >= 0:
                return True
        return False
    
    def expand(self, pos, word, used):
        if not word:
            return True
        for step in [(1,0), (0,1), (-1,0), (0,-1)]:
            x,y = (pos[0] + step[0],pos[1] + step[1])
            if (x,y) not in used and self.issafe(x,y):
                neighbor = self.board[x][y]
                if neighbor == word[0]:
                    if self.expand((x,y), word[1:], used + [(x,y)]):
                        return True
              
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.board = board
        seq = set([j for i in board for j in i])
        for char in word:
            if char not in seq:
                return False
        self.width, self.height = len(board[0]), len(board)
        for j in range(self.height):
            for k in range(self.width):
                char = board[j][k]
                if char == word[0]:
                    if self.expand((j,k), word[1:], [(j,k)]):
                        return True
        return False