Ver2.py

class Solution2:
	# @param {character[][]} board
	# @param {string} word
	# @return {boolean}
	def exist(self, board, word):
		def dfs(index, word, rec):
			if not word:
				return True
			elif index in rec or index[0]<0 or index[0]>=len(board) \
				or index[1] < 0 or index[1]>=len(board[index[0]]):
				return False

			if board[index[0]][index[1]] == word[0]:
				rec.add(index)
				return dfs((index[0]+1, index[1]), word[1:len(word)], set(rec)) \
					or dfs((index[0]-1, index[1]), word[1:len(word)], set(rec)) \
					or dfs((index[0], index[1]+1), word[1:len(word)], set(rec)) \
					or dfs((index[0], index[1]-1), word[1:len(word)], set(rec))
			else:
				return False
				
		if not board:
			return False
		# elif len(board) == 1:
		# 	board = [board, ["", ""]]
		
		for i in xrange(len(board)):
			if type(board[i]) == list:
				board[i] = board[i][0]

		word = list(word)
		for i in xrange(len(board)):
			for j in xrange(len(board[i])):
				if board[i][j] == word[0] and dfs((i, j), list(word), set()):
					return True

		return False