106 ms python solution


  • 0
    W

    class Solution(object):

    # The solution is:
    # First of all, check the length of the word 
    # if the length of the word > size of the board. Board impossible contains the word
    # after that, checking whether the borad contains the possible solution. check function is designed for that
    # then use the DSP to find a solution
    # dsp contains for different move. there are: go up, go down, go left, and go right.
    # when you do your move, first of all, make sure next move is in bound
    # To avoid repeat Selection. once you make a move. mark that space. I use the " "
    # sometimes, you move don't have a solution. e.g, you go right first, but after traversal,
    # right doesn't have a solution. Then, you will check another direction
    # in this situation, remember reset the original space. when you 
    # go other direction, you don't want right space have your marking
    # when you find a solution, return True. no solution return False
    
    
    def check(self,board,word):
    	# buf store all elements of the board
    	# ind store all elemts of the word
    	buf = []
    	ind = []
    
    	for i in word:
    		buf.append(i)
    
    	for row in range(len(board)):
    
    		for column in range(len(board[0])):
    
    			# print board[row][column]
    			ind.append(board[row][column])
    	i = 0
    	# check whether board contains a possible solution
    	while i in range(len(buf)):
    
    		if buf[i] in ind:
    			ind.remove(buf[i])
    			buf.remove(buf[i])
    		else:
    			return False
    
    	if not buf:
    		return True
    	else:
    		return False
    
    
    def dfs(self,board, word, row, column):
    
    	# first store the original value
    	# if one direction no solution
    	# reset the space and check the other direction
    	first = word[0]
    	word = word[1:]
    
    	if len(word) == 0:
    		return True
    
    	board[row][column] = " "
    	row_next = row + 1
    	row_last = row - 1
    	column_next = column + 1
    	column_last = column - 1
    
    	# go right
    	if column_next <= len(board[0]) - 1:
    		if word[0] == board[row][column_next]:
    			if self.dfs(board,word,row,column_next):
    				return True
    	# go down
    	if row_next <= len(board) - 1:
    		if word[0] == board[row_next][column]:
    			if self.dfs(board,word,row_next,column):
    				return True
    	# go up
    	if row_last >= 0:
    		if word[0] == board[row_last][column]:
    			if self.dfs(board,word,row_last,column):
    				return True
    	# go left
    	if column_last >= 0:
    		if word[0] == board[row][column_last]:
    			if self.dfs(board,word,row,column_last):
    				return True
    
    	board[row][column] = first
    
    	return False
    
    def exist(self,board, word):
    
    	if not word:
    
    		return True
    
    	if not board:
    
    		return False
    
    	if len(word) > len(board) * len(board[0]):
    		return False
    
    	if self.check(board , word) == False:
    		return False
    
    	for row in range(len(board)):
    
    		for column in range(len(board[0])):
    
    			if board[row][column] == word[0]:
    
    				if self.dfs(board,word,row,column):
    					return True
    
    	return False

  • 0
    W

    if you have a issue about my code. you can leave your question or email me. I'm happy to reply your issue


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.