Jul 2, 2022 · Jun 19, 2022
diff --git a/212-Word-Search-II.py b/212-Word-Search-II.py
    def __init__(self):
        self.children = {}
        self.isWord = False
        self.refs = 0

    def addWord(self, word):
        cur = self
        cur.refs += 1
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
            cur.refs += 1
        cur.isWord = True

    def removeWord(self, word):
        cur = self
        cur.refs -= 1
        for c in word:
            if c in cur.children:
                cur = cur.children[c]
                cur.refs -= 1


 class Solution:
        def dfs(r, c, node, word):
            if (r < 0 or c < 0 or
                r == ROWS or c == COLS or
                board[r][c] not in node.children or (r, c) in visit):
                board[r][c] not in node.children or
                node.children[board[r][c]].refs < 1 or
                (r, c) in visit):
                return

            visit.add((r, c))
            node = node.children[board[r][c]]
            word += board[r][c]
            if node.isWord:
                node.isWord = False
                res.add(word)
                root.removeWord(word)

            dfs(r + 1, c, node, word)
            dfs(r - 1, c, node, word)
Original file line number	Diff line number	Diff line change
Expand Up		@@ -2,14 +2,25 @@ class TrieNode:
		def __init__(self):
		self.children = {}
		self.isWord = False
		self.refs = 0

		def addWord(self, word):
		cur = self
		cur.refs += 1
		for c in word:
		if c not in cur.children:
		cur.children[c] = TrieNode()
		cur = cur.children[c]
		cur.refs += 1
		cur.isWord = True

		def removeWord(self, word):
		cur = self
		cur.refs -= 1
		for c in word:
		if c in cur.children:
		cur = cur.children[c]
		cur.refs -= 1


		class Solution:
Expand All		@@ -24,14 +35,18 @@ def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
		def dfs(r, c, node, word):
		if (r < 0 or c < 0 or
		r == ROWS or c == COLS or
		board[r][c] not in node.children or (r, c) in visit):
		board[r][c] not in node.children or
		node.children[board[r][c]].refs < 1 or
		(r, c) in visit):
		return

		visit.add((r, c))
		node = node.children[board[r][c]]
		word += board[r][c]
		if node.isWord:
		node.isWord = False
		res.add(word)
		root.removeWord(word)

		dfs(r + 1, c, node, word)
		dfs(r - 1, c, node, word)
Expand Down