Word Search

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
class Solution(object):
def exist(self, board, word):
“””
:type board: List[List[str]]
:type word: str
:rtype: bool
“””
# find the first element
# dfs
# mark current visited
# dfs next layer with word[1:]
self.ans = False
rowNum = len(board)
colNum = len(board[0])
visited = [[0 for _ in range(colNum)] for _ in range(rowNum)]
direction = [(0, 1), (1,0), (-1, 0), (0, -1)]
word = list(word)
def dfs(i, j, newWord, pos):
if visited[i][j] == 1 or self.ans:
return
visited[i][j] = 1
if pos == len(newWord)-1:
self.ans = True
return

for each in direction:
x, y = i+each[0], j+each[1]
if x < 0 or x >= rowNum or y < 0 or y >= colNum or board[x][y] != newWord[pos+1]:
continue
dfs(x, y, newWord, pos+1)
visited[i][j] = 0


for i in range(rowNum):
for j in range(colNum):
if board[i][j] == word[0]:
dfs(i,j, word, 0)
if self.ans == True:
return self.ans
return self.ans

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

What feels like the end is often the beginning

Java Spring Gateway — Connection prematurely closed

10 Usually Forgotten, but Useful Shortcuts in Windows 10

Kainos WebOps Academy: April-June 2018

Liquidity Mining Workshop

Applied C++: Memory Latency

Building a GraphQL API with Ruby on Rails

How to connect multiple Mongo DB Databases with Spring Boot

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Newbie Developer

Newbie Developer

More from Medium

Dilemma of choosing career

Blog Post- Big Data

Building a Web Dev Portfolio with React

Coding: Learning (Yet) Another Language