Palindrome Partitioning @ LeetCode (Python)
Gray Code @ LeetCode (Python)

Word Search @ LeetCode (Python)

kitt posted @ 2014年4月09日 11:59 in LeetCode , 4318 阅读

使用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
Avatar_small
fi 说:
2014年4月24日 02:31

would you please give the time and space complexity for this problem?
Thank you so much!

Avatar_small
xyz 说:
2014年7月08日 13:12

替换成#的方法好巧妙!这样就不用数组记录visited了~赞

Avatar_small
zyx 说:
2014年9月02日 00:43

string类不应该是immutable么

为什么下一行能通过?
ch, board[r][c] = board[r][c], '#'

Avatar_small
dbs 说:
2015年7月31日 21:55

@zyx: 他这个过不了

Avatar_small
NCERT Evs Sample Pap 说:
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.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter