Question: https://oj.leetcode.com/problems/word-search/
Question Name: Word Search
The description and comments are misleading. Comments says “@param board, a list of lists of 1 length string”. And in the example, the input board is [[“ABCE”], [“SFCS”], [“ADEE”]]. But actually, in the tests, the board is a list of same length string, like [“ABCE”, “SFCS”, “ADEE”].
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | class Solution: # @param board, a list of same length string # @param currentRow, the row position of current standing cell # @param currentCol, the column position of current standing cell # @param accessed, a list of list of boolean # @param word, a string # @param wordIndex, the index of next processing letter in word # @return a boolean def existHelper(self, board, currentRow, currentCol, accessed, word, wordIndex): if wordIndex == len(word): # Find a path to match word completely return True # Try to move to the upper cell if currentRow != 0 and accessed[currentRow-1][currentCol] == False and board[currentRow-1][currentCol] == word[wordIndex]: accessed[currentRow-1][currentCol] = True res = self.existHelper(board, currentRow-1, currentCol, accessed, word, wordIndex+1) if res == True: return True # Find a path to match word accessed[currentRow-1][currentCol] = False # Try to move to the lower cell if currentRow != len(board) - 1 and accessed[currentRow+1][currentCol] == False and board[currentRow+1][currentCol] == word[wordIndex]: accessed[currentRow+1][currentCol] = True res = self.existHelper(board, currentRow+1, currentCol, accessed, word, wordIndex+1) if res == True: return True # Find a path to match word accessed[currentRow+1][currentCol] = False # Try to move to the left cell if currentCol != 0 and accessed[currentRow][currentCol-1] == False and board[currentRow][currentCol-1] == word[wordIndex]: accessed[currentRow][currentCol-1] = True res = self.existHelper(board, currentRow, currentCol-1, accessed, word, wordIndex+1) if res == True: return True # Find a path to match word accessed[currentRow][currentCol-1] = False # Try to move to the right cell if currentCol != len(board[0]) - 1 and accessed[currentRow][currentCol+1] == False and board[currentRow][currentCol+1] == word[wordIndex]: accessed[currentRow][currentCol+1] = True res = self.existHelper(board, currentRow, currentCol+1, accessed, word, wordIndex+1) if res == True: return True # Find a path to match word accessed[currentRow][currentCol+1] = False # No path is found to match word return False # @param board, a list of same length string # @param word, a string # @return a boolean def exist(self, board, word): # Record which cells have been accessed accessed = [[False]*len(board[0]) for _ in board] for rowIndex in xrange(len(board)): for colIndex in xrange(len(board[0])): # Start a new path if board[rowIndex][colIndex] == word[0]: accessed[rowIndex][colIndex] = True res = self.existHelper(board, rowIndex, colIndex, accessed, word, 1) if res == True: return True # Find a path to match word accessed[rowIndex][colIndex] = False # No path is found to match word return False |