Word Search I.py

class TrieNode:
    def __init__(self):
        self.childen = {}
        self.isEnd = False
        self.refs = 0

    def addWord(self,word):
        cur = self
        # cur.ref += 1
        for w in word:
            if w not in cur.childen:
                cur.childen[w] =  TrieNode()
            cur = cur.childen[w]
            cur.refs +=1      
        cur.isEnd = True
    def removeWord(self,word):
        cur = self
        # cur.ref -= 1
        for c in word:
            if c in cur.childen:
                cur = cur.childen[c]
                cur.refs -= 1
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        root = TrieNode()

        root.addWord(word)

        ROWS,COLS = len(board) , len(board[0])

        visited , res = set(), set()

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

            node = node.childen[board[r][c]]

            word = word + board[r][c]
            if node.isEnd:
                res.add(word)
                node.isEnd = False
                root.removeWord(word)

            visited.add((r,c))

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

            visited.remove((r,c))

        for r in range(ROWS):
            for c in range(COLS):
                dfs(r,c,root,"")
        
        if len(res) == 0:
            return False
        else:
            return True