# Python DFS solution

• ``````class Solution:
# @param board, a list of lists of 1 length string
# @param word, a string
# @return a boolean
# 3:42
def exist(self, board, word):
visited = {}

for i in range(len(board)):
for j in range(len(board[0])):
if self.getWords(board, word, i, j, visited):
return True

return False

def getWords(self, board, word, i, j, visited, pos = 0):
if pos == len(word):
return True

if i < 0 or i == len(board) or j < 0 or j == len(board[0]) or visited.get((i, j)) or word[pos] != board[i][j]:
return False

visited[(i, j)] = True
res = self.getWords(board, word, i, j + 1, visited, pos + 1) \
or self.getWords(board, word, i, j - 1, visited, pos + 1) \
or self.getWords(board, word, i + 1, j, visited, pos + 1) \
or self.getWords(board, word, i - 1, j, visited, pos + 1)
visited[(i, j)] = False

return res``````

• Great Code! I previously use code like

``````dfs()
visited[i-1,j] = true;
dfs(i-1,j)
visited[i-1,j] = false;

visited[i+1,j] = true;
dfs(i+1,j)
visited[i+1,j] = false;

visited[i,j-1] = true;
dfs(i,j-1)
visited[i,j-1] = false;

visited[i,j+1] = true;
dfs(i,j+1)
visited[i,j+1] = false;
``````

and get TLE for {"aaaa...","aaaa...."} case. Still dont' understand what's the difference

Modified java code based on your idea.

``````public class Solution {
public boolean exist(char[][] board, String word) {
// edge case
if(word == null || board == null || board.length == 0) return false;

boolean[][] used = new boolean[board.length][board[0].length];
for(int i = 0;i < board.length;i++)
for(int j = 0;j < board[0].length;j++)
if(dfs(board, i, j, word, 0, used)) return true;
return false;
}

private boolean dfs(char[][] board, int x, int y, String word, int index, boolean[][] used){
// ending case
if(index==word.length()) return true;

if(x < 0 || x >= board.length || y < 0 || y >= board[0].length) return false;

if(used[x][y] || board[x][y]!=word.charAt(index)) return false;

// recursive call
used[x][y] = true;
if(dfs(board,x-1,y,word,index+1,used)) return true;
if(dfs(board,x+1,y,word,index+1,used)) return true;
if(dfs(board,x,y-1,word,index+1,used)) return true;
if(dfs(board,x,y+1,word,index+1,used)) return true;
used[x][y] = false;

return false;
}
}
``````

• It is curious that or instead of "|" can be accepted, something to do with parallelism?

• Where is it?

• here is the code

class Solution:
def f(self,board,word,i,j,visited,pos=0):
if len(word)==pos:
return True
if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or visited.get((i,j)) or word[pos]!=board[i][j]:
return False

``````    visited[(i,j)]=True

res=self.f(board,word,i,j+1,visited,pos+1)\
|self.f(board,word,i ,j-1,visited,pos+1)\
|self.f(board,word,i+1,j ,visited,pos+1)\
|self.f(board,word,i-1,j,visited,pos+1)
visited[(i,j)]=False
return res
# @param board, a list of lists of 1 length string
# @param word, a string
# @return a boolean
def exist(self, board, word):

visited={}

for i in range(len(board)):
for j in range(len(board[0])):
#print i,j
if self.f(board,word,i,j,visited):
return True

return False
``````

change '|' to 'or' will TLE

• "|" is a binary operator, whereas "or" is a logical operator, which means "or" will stop once True is met, "|" won't. That's the difference.

• I see now, just like the difference between | and || in C++, thank you very much!

• Nice idea, here is a revised version of your code:

``````def exist(self, board, word):
if not board:
return False
r, c = len(board), len(board[0])
visited = [[False for i in xrange(c)] for j in xrange(r)]
for i in xrange(r):
for j in xrange(c):
if self.dfs(board, word, visited, i, j):
return True
return False

def dfs(self, board, word, visited, i, j):
if not word:
return True
if i < 0 or i == len(board) or j < 0 or j == len(board[0]) \
or visited[i][j] or word[0] != board[i][j]:
return False
visited[i][j] = True
res = self.dfs(board, word[1:], visited, i+1, j) or \
self.dfs(board, word[1:], visited, i-1, j) or \
self.dfs(board, word[1:], visited, i, j-1) or \
self.dfs(board, word[1:], visited, i, j+1)
visited[i][j] = False
return res``````

• Could you explain what does visited[(i,j)]=False mean?

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