212. Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.
Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

My Answer 1: Accepted (Runtime: 44 ms - 70.35% / Memory Usage: 14.1 MB - 97.70%)

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        ## RC ##
        ## RECURSIVE ##
        ## similar to Number of Islands ##
        def search(board, i, j, word):
            
            if(len(word) == 0):
                return True
            
            if(i < 0  or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[0]):
                return False
            
            temp = board[i][j]
            board[i][j] = '$'
            
            result = search(board, i+1, j, word[1:]) or search(board, i-1, j, word[1:]) or search(board, i, j+1, word[1:]) or search(board, i, j-1, word[1:])
            
            board[i][j] = temp
            return result
        
        res = []
        for word in words:
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if search(board, i, j, word):           
                        res.append(word)
                        break
                        
        res = list(set(res))
        
        return res

以前にリリースされた79. Word Searchコードを少し修正しました
wordsのwordを1つずつ検索し、最後にres = list(set(res))を使用して重複データ除去を行います.
でもこれは三重forゲートです…^^

Trie with DFS

Solution 1: Runtime: 9816 ms -5.00% / Memory Usage: 14.4 MB - 46.27%

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        ## RC ##
		## APPROACH : TRIE + DFS ##
		## LOGIC ##
		#	1. build trie with all words list
		#	2. start scanning matrix, move in all four directions and check if such combination exists in the trie
		#	3. make sure you donot return when result is found ( case: words = [cat, cattle ] )
		
        ## TIME COMPLEXICITY : O(M(4x3^(L-1))) ## (M is the number of cells in the board and L is the maximum length of words.)
		## SPACE COMPLEXICITY : O(N) ##
	    
        def dfs(i, j, curr, currNode):
            ch = board[i][j]
            if( ch not in currNode.children or (i, j) in visited ):
                return
            if currNode.children[ch].endOfWord:
                res.add(curr)
                # return                            # edge case
            visited.add((i,j))
            for x,y in directions:
                if 0 <= i + x < m and 0 <= j + y < n:
                    dfs( i + x, j + y, curr + board[i + x][j + y], currNode.children[ch])
            visited.remove((i,j))   # edge case
        
        # buid trie data structure
        my_trie = Trie()
        [ my_trie.insert(word) for word in words ]
        rootNode = my_trie.get_rootNode()
        
        m, n = len(board), len(board[0])
        directions = [(0,1), (1,0), (0,-1), (-1,0)]
        res = set()                     
        for i in range(len(board)):
            for j in range(len(board[i])):
                visited = set()
                dfs(i, j, board[i][j], rootNode)
        return res
    
class TrieNode:
    def __init__(self):
        self.children = {}
        self.endOfWord = False

class Trie:
    def __init__(self):
        self.rootNode = TrieNode()
    
    def get_rootNode(self):
        return self.rootNode
    
    # Inserts a word into the trie.
    def insert(self, word: str) -> None:
        currNode = self.rootNode
        for idx, ch in enumerate(word):
            if( ch not in currNode.children ):
                currNode.children[ch] = TrieNode()
            currNode = currNode.children[ch]        
        currNode.endOfWord = True

運行時間はそうですが…本当にTrieが1つずつ書いているようですが….
Treeを作成し、単語の単語をtrieにすべて挿入します.
resは重複しない集合として作成され、dfsが提供される.
彼らに見学した場所をスキップさせる
dfs)
1.テキストはcurrNodeです.子供たちのところにいないか、訪問した場所にいないなら、帰ってきてください.
2.メールがあったら、最後のメールを見つけてresに入れる
3.その他に次の文字を検索する必要があります.for x,y in directions:に検索する文字があるかどうかを確認してください.
=>dfs再帰
4.最後にvisited.remove((i,j))の他の単語を探す