079. Word Search

#!/usr/bin/env python3

__author__ = 'Wei Mu'

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if len(board) * len(board[0]) < len(word):
            return False
        
        loc_list = []
        used_index = []
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    loc_list.append([i, j])
        
        for loc in loc_list:
            used_index.append([loc[0],loc[1]])
            if self.helper_func(board, word[1:], loc, used_index) == True:
                return True
            used_index.pop()
        return False
    
    def helper_func(self, board, word, loc, used_index):
        if word == '':
            return True
        
        orig_row, orig_col = loc[0], loc[1]
        
        ans = False
        
        for (i, j) in [(0, -1), (0, 1), (-1, 0), (1,0)]:
            row = orig_row + i
            col = orig_col + j
            
            if row < 0 or row > len(board) - 1 or col < 0 or col > (len(board[0])) - 1 or [row, col] in used_index:
                continue
            
            if board[row][col] == word[0]:
                used_index.append([row, col])
                if self.helper_func(board, word[1:], [row, col], used_index):
                    return True
                used_index.pop()
        
        return False