Word Search @ LeetCode (Python)
kitt
posted @ 2014年4月09日 11:59
in LeetCode
, 4337 阅读
使用DFS, 不要再开一个新的棋盘或其他很大的变量来记录状态,不然容易超时。
Use DFS. Don't make a new board or other large variables to record state, or it's easy to TLE.
class Solution: # @param {character[][]} board # @param {string} word # @return {boolean} def exist(self, board, word): self.b, self.w, self.m, self.n, self.wLen = board, word, len(board), len(board[0]), len(word) for i in xrange(self.m): for j in xrange(self.n): if self.isFound(0, i, j): return True return False def isFound(self, k, x, y): if x < 0 or y < 0 or x >= self.m or y >= self.n or self.b[x][y] == '.' or self.b[x][y] != self.w[k]: return False if k == self.wLen - 1: return True tmp, self.b[x][y] = self.b[x][y], '.' if self.isFound(k + 1, x - 1, y) or self.isFound(k + 1, x + 1, y) or \ self.isFound(k + 1, x, y - 1) or self.isFound(k + 1, x, y + 1): return True self.b[x][y] = tmp return False
2014年4月24日 02:31
would you please give the time and space complexity for this problem?
Thank you so much!
2014年7月08日 13:12
替换成#的方法好巧妙!这样就不用数组记录visited了~赞
2014年9月02日 00:43
string类不应该是immutable么
为什么下一行能通过?
ch, board[r][c] = board[r][c], '#'
2015年7月31日 21:55
@zyx: 他这个过不了
2015年8月01日 14:21
已更新 @dbs:
2022年9月16日 11:21
Environmental Education or Environmental Studies (EVS) was introduced from the foundation of education to enable students to understand the situations occurring around our surroundings without any difficulties. NCERT Evs Sample Paper Class 2 The subject refers to the neighbouring in which all life, also makes use of to solve day-to-day challenges involving the environmental elements.To get a complete analysis of examination question pattern and to get ready to write an exam with confidence, subject experts of the NCERT has provided the Class 2 EVS Sample Paper 2023 with study & learning material that supports all formats of exams held under Term-1, Term-2 and other types of exams for every interested candidate.